{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Quad Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #array #divide-and-conquer #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #数组 #分治 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: construct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #建立四叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>n * n</code> 矩阵 <code>grid</code> ，矩阵由若干 <code>0</code> 和 <code>1</code> 组成。请你用四叉树表示该矩阵 <code>grid</code> 。</p>\n",
    "\n",
    "<p>你需要返回能表示矩阵 <code>grid</code> 的 四叉树 的根结点。</p>\n",
    "\n",
    "<p>四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>val</code>：储存叶子结点所代表的区域的值。1 对应 <strong>True</strong>，0 对应 <strong>False</strong>。注意，当 <code>isLeaf</code> 为 <strong>False </strong>时，你可以把 <strong>True</strong> 或者 <strong>False</strong> 赋值给节点，两种值都会被判题机制 <strong>接受</strong> 。</li>\n",
    "\t<li><code>isLeaf</code>: 当这个节点是一个叶子结点时为 <strong>True</strong>，如果它有 4 个子节点则为 <strong>False</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<pre>\n",
    "class Node {\n",
    "    public boolean val;\n",
    "&nbsp; &nbsp; public boolean isLeaf;\n",
    "&nbsp; &nbsp; public Node topLeft;\n",
    "&nbsp; &nbsp; public Node topRight;\n",
    "&nbsp; &nbsp; public Node bottomLeft;\n",
    "&nbsp; &nbsp; public Node bottomRight;\n",
    "}</pre>\n",
    "\n",
    "<p>我们可以按以下步骤为二维区域构建四叉树：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>如果当前网格的值相同（即，全为 <code>0</code> 或者全为 <code>1</code>），将 <code>isLeaf</code> 设为 True ，将 <code>val</code> 设为网格相应的值，并将四个子节点都设为 Null 然后停止。</li>\n",
    "\t<li>如果当前网格的值不同，将 <code>isLeaf</code> 设为 False， 将 <code>val</code> 设为任意值，然后如下图所示，将当前网格划分为四个子网格。</li>\n",
    "\t<li>使用适当的子网格递归每个子节点。</li>\n",
    "</ol>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/new_top.png\" style=\"height: 181px; width: 777px;\" /></p>\n",
    "\n",
    "<p>如果你想了解更多关于四叉树的内容，可以参考 <a href=\"https://en.wikipedia.org/wiki/Quadtree\">wiki</a> 。</p>\n",
    "\n",
    "<p><strong>四叉树格式：</strong></p>\n",
    "\n",
    "<p>你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 <code>null</code> 表示路径终止符，其下面不存在节点。</p>\n",
    "\n",
    "<p>它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 <code>[isLeaf, val]</code> 。</p>\n",
    "\n",
    "<p>如果 <code>isLeaf</code> 或者 <code>val</code> 的值为 True ，则表示它在列表&nbsp;<code>[isLeaf, val]</code> 中的值为 <strong>1</strong> ；如果 <code>isLeaf</code> 或者 <code>val</code> 的值为 False ，则表示值为 <strong>0 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/grid1.png\" style=\"height: 99px; width: 777px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,1],[1,0]]\n",
    "<strong>输出：</strong>[[0,1],[1,0],[1,1],[1,1],[1,0]]\n",
    "<strong>解释：</strong>此示例的解释如下：\n",
    "请注意，在下面四叉树的图示中，0 表示 false，1 表示 True 。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/12/e1tree.png\" style=\"height: 186px; width: 777px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/12/e2mat.png\" style=\"height: 343px; width: 777px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]\n",
    "<strong>输出：</strong>[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]\n",
    "<strong>解释：</strong>网格中的所有值都不相同。我们将网格划分为四个子网格。\n",
    "topLeft，bottomLeft 和 bottomRight 均具有相同的值。\n",
    "topRight 具有不同的值，因此我们将其再分为 4 个子网格，这样每个子网格都具有相同的值。\n",
    "解释如下图所示：\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/12/e2tree.png\" style=\"height: 328px; width: 777px;\" />\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>n == 2<sup>x</sup></code> 其中 <code>0 &lt;= x &lt;= 6</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-quad-tree](https://leetcode.cn/problems/construct-quad-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-quad-tree](https://leetcode.cn/problems/construct-quad-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,0]]', '[[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def judgeNode(split_list, preorder):\n",
    "            if len(split_list) == 1:  # 叶子结点则构造节点\n",
    "                node = TreeNode(split_list[0])\n",
    "                # print(split_list[0])\n",
    "                preorder.remove(split_list[0])\n",
    "                return node\n",
    "            elif len(split_list)>1:  # 不是叶子结点，则找出当前根节点\n",
    "                return constructNode(preorder[-1], preorder, split_list)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        def constructNode(num, preorder, inorder):\n",
    "            # print(num)\n",
    "            node = TreeNode(num)\n",
    "            preorder.remove(num)\n",
    "            index = inorder.index(num)\n",
    "\n",
    "            # 划分中序的左右两段\n",
    "            split_left = inorder[:index]\n",
    "            split_right = inorder[index + 1:]\n",
    "            node.right = judgeNode(split_right, preorder)\n",
    "            node.left = judgeNode(split_left, preorder)\n",
    "            \n",
    "            return node\n",
    "\n",
    "        # 前序确定根节点，中序确定左右节点\n",
    "        head = constructNode(postorder[-1], postorder, inorder)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def buildTree(self, preorder, inorder):\n",
    "        \"\"\"\n",
    "        :type preorder: List[int]\n",
    "        :type inorder: List[int]\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "\t# construct hashmap mapping a value to its inorder index\n",
    "        idx = {} \n",
    "        for i, val in enumerate(inorder):\n",
    "            idx[val] = i \n",
    "\t\t\t\n",
    "\t# Iterate over preorder and construct the tree \n",
    "        stack = []\n",
    "        head = None\n",
    "        for val in preorder:\n",
    "            if not head:\n",
    "                head = TreeNode(val)\n",
    "                stack.append(head)\n",
    "            else:\n",
    "                node = TreeNode(val)\n",
    "                if idx[val] < idx[stack[-1].val]:\n",
    "                    stack[-1].left = node\n",
    "                else:\n",
    "                    while stack and idx[stack[-1].val] < idx[val]:\n",
    "                        u = stack.pop()\n",
    "                    u.right = node\n",
    "                stack.append(node)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def judgeNode(split_list, preorder):\n",
    "            if len(split_list) == 1:  # 叶子结点则构造节点\n",
    "                node = TreeNode(split_list[0])\n",
    "                # print(split_list[0])\n",
    "                preorder.remove(split_list[0])\n",
    "                return node\n",
    "            elif len(split_list)>1:  # 不是叶子结点，则找出当前根节点\n",
    "                print(preorder[0])\n",
    "                return constructNode(preorder[0], preorder, split_list)\n",
    "            else:\n",
    "                return None\n",
    "\n",
    "        def constructNode(num, preorder, inorder):\n",
    "            # print(num)\n",
    "            node = TreeNode(num)\n",
    "            preorder.remove(num)\n",
    "            index = inorder.index(num)\n",
    "\n",
    "            # 划分中序的左右两段\n",
    "            split_left = inorder[:index]\n",
    "            split_right = inorder[index + 1:]\n",
    "            node.left = judgeNode(split_left, preorder)\n",
    "            node.right = judgeNode(split_right, preorder)\n",
    "            return node\n",
    "\n",
    "        # 前序确定根节点，中序确定左右节点\n",
    "        head = constructNode(preorder[0], preorder, inorder)\n",
    "        return head\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self) -> None:\r\n",
    "        self.valtoIndex={}\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        for i in range(len(postorder)):\r\n",
    "            self.valtoIndex[postorder[i]]=i\r\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\r\n",
    "    \r\n",
    "    def build(self,preorder,prestart,preend,postorder,poststart,postend):\r\n",
    "        if prestart>preend:\r\n",
    "            return \r\n",
    "        if prestart==preend:\r\n",
    "            return TreeNode(preorder[prestart])\r\n",
    "        \r\n",
    "        rootVal=preorder[prestart]\r\n",
    "        leftrootval=preorder[prestart+1]\r\n",
    "        index=self.valtoIndex[leftrootval]\r\n",
    "\r\n",
    "        leftsize=index-poststart+1\r\n",
    "        root=TreeNode(rootVal)\r\n",
    "        root.left=self.build(preorder,prestart+1,prestart+leftsize,postorder,poststart,index)\r\n",
    "        root.right=self.build(preorder,prestart+leftsize+1,preend,postorder,index+1,postend-1)\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:\n",
    "        if not pre and not post:\n",
    "            return None\n",
    "        if pre[0]==post[0]:\n",
    "            return TreeNode(pre[0])\n",
    "        root = TreeNode(pre[0])\n",
    "        i,j=1,0\n",
    "        while pre[i]!=post[j]:\n",
    "            j+=1\n",
    "        root.left=self.constructFromPrePost(pre[1:j+2],post[0:j+1])\n",
    "        root.right=self.constructFromPrePost(pre[j+2:],post[j+1:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        root = TreeNode(val=preorder[0])\n",
    "        if len(preorder) == 1: return root\n",
    "        i = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:i+1], postorder[:i])\n",
    "        root.right = self.constructFromPrePost(preorder[i+1:], postorder[i:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(preorder[0])\n",
    "        for node in preorder[1:]:\n",
    "            last = None\n",
    "            cur = root\n",
    "            nxt = None\n",
    "            while cur:\n",
    "                if postorder.index(node) < postorder.index(cur.val):\n",
    "                    last = cur\n",
    "                    cur = last.left\n",
    "                    nxt = last.right\n",
    "                elif postorder.index(node) > postorder.index(cur.val):\n",
    "                    cur = nxt\n",
    "            if last.left == None: last.left = TreeNode(node)\n",
    "            else: last.right = TreeNode(node)\n",
    "            \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self):\r\n",
    "        # 存储 postorder 中值到索引的映射\r\n",
    "        self.valToIndex = {}\r\n",
    "\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\r\n",
    "        for i in range(len(postorder)):\r\n",
    "            self.valToIndex[postorder[i]] = i\r\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\r\n",
    "\r\n",
    "    # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\r\n",
    "    def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\r\n",
    "        if preStart > preEnd:\r\n",
    "            return None\r\n",
    "        if preStart == preEnd:\r\n",
    "            return TreeNode(preorder[preStart])\r\n",
    "\r\n",
    "        # root 节点对应的值就是前序遍历数组的第一个元素\r\n",
    "        rootVal = preorder[preStart]\r\n",
    "        # root.left 的值是前序遍历第二个元素\r\n",
    "        # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\r\n",
    "        # 确定 preorder 和 postorder 中左右子树的元素区间\r\n",
    "        leftRootVal = preorder[preStart + 1]\r\n",
    "        # leftRootVal 在后序遍历数组中的索引\r\n",
    "        index = self.valToIndex[leftRootVal]\r\n",
    "        # 左子树的元素个数\r\n",
    "        leftSize = index - postStart + 1\r\n",
    "\r\n",
    "        # 先构造出当前根节点\r\n",
    "        root = TreeNode(rootVal)\r\n",
    "        # 递归构造左右子树\r\n",
    "        # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\r\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\r\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\r\n",
    "\r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "\n",
    "\n",
    "    # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\n",
    "    def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "\n",
    "        # root 节点对应的值就是前序遍历数组的第一个元素\n",
    "        rootVal = preorder[preStart]\n",
    "        # root.left 的值是前序遍历第二个元素\n",
    "        # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\n",
    "        # 确定 preorder 和 postorder 中左右子树的元素区间\n",
    "        leftRootVal = preorder[preStart + 1]\n",
    "        # leftRootVal 在后序遍历数组中的索引\n",
    "        index = postorder.index(leftRootVal)\n",
    "        # 左子树的元素个数\n",
    "        leftSize = index - postStart + 1\n",
    "\n",
    "        # 先构造出当前根节点\n",
    "        root = TreeNode(rootVal)\n",
    "        # 递归构造左右子树\n",
    "        # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.valToIndex = {}\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.valToIndex[postorder[i]]=i\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        \n",
    "        rootVal = preorder[preStart]\n",
    "        root = TreeNode(rootVal)\n",
    "        if preStart == preEnd:\n",
    "            return root\n",
    "        \n",
    "        # 后序序列中左子树的根节点的index\n",
    "        index = self.valToIndex[preorder[preStart+1]]\n",
    "        leftSize = index - postStart + 1\n",
    "        root.left = self.build(preorder, preStart+1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize+1, preEnd, postorder, index+1,postEnd-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return\n",
    "        root = TreeNode(val = preorder[0])\n",
    "        preorderL = None\n",
    "        preorderR = None\n",
    "        postorderL = None\n",
    "        postorderR = None\n",
    "        restPreorder = preorder[1:]\n",
    "        restPostorder = postorder[:-1]\n",
    "        if len(restPreorder) == 1:\n",
    "            root.left = TreeNode(restPreorder[0])\n",
    "            return root\n",
    "        for i in range(1, len(restPreorder) + 1):\n",
    "            if set(restPreorder[:i]) == set(restPostorder[:i]) and\\\n",
    "            set(restPreorder[i:]) == set(restPostorder[i:]):\n",
    "                preorderL = restPreorder[:i]\n",
    "                postorderL = restPostorder[:i]\n",
    "                preorderR = restPreorder[i:]\n",
    "                postorderR = restPostorder[i:]\n",
    "                break\n",
    "        # print(preorderL, preorderR)\n",
    "        # print(postorderL, postorderR)\n",
    "        root.left = self.constructFromPrePost(preorderL, postorderL)\n",
    "        root.right = self.constructFromPrePost(preorderR, postorderR)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(preorder.pop(0))\n",
    "        postorder.pop()\n",
    "\n",
    "        if preorder and preorder[0] == postorder[-1]:\n",
    "            root.left = self.constructFromPrePost(preorder, postorder)\n",
    "        elif preorder:\n",
    "            l_len = postorder.index(preorder[0]) + 1\n",
    "            root.left = self.constructFromPrePost(preorder[:l_len], postorder[:l_len])\n",
    "            root.right = self.constructFromPrePost(preorder[l_len:], postorder[l_len:])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.preindex, self.posindex = 0, 0\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode(preorder[self.preindex])\n",
    "        self.preindex += 1\n",
    "        if postorder[self.posindex] != root.val:\n",
    "            root.left = self.constructFromPrePost(preorder, postorder)\n",
    "        if postorder[self.posindex] != root.val:\n",
    "            root.right = self.constructFromPrePost(preorder, postorder)\n",
    "        self.posindex += 1\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return node\n",
    "        idx = postorder.index(preorder[1])\n",
    "        node.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        node.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        tree = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return tree\n",
    "        i = postorder.index(preorder[1])\n",
    "        left_pre = preorder[1:i+2]\n",
    "        left_post = postorder[:i+1]\n",
    "        right_pre = preorder[i+2:]\n",
    "        right_post = postorder[i+1:-1]\n",
    "        # print(left_pre,left_post,right_pre,right_post)\n",
    "        tree.left = self.constructFromPrePost(left_pre,left_post)\n",
    "        tree.right = self.constructFromPrePost(right_pre,right_post)\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left_count = postorder.index(preorder[1])+1\n",
    "        root.left = self.constructFromPrePost(preorder[1:left_count+1],postorder[:left_count])\n",
    "        root.right = self.constructFromPrePost(preorder[left_count+1:],postorder[left_count:-1])\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        #拆分左右\n",
    "        L = postorder.index(preorder[1]) #左子树结束位置\n",
    "        #递归左右\n",
    "        leftroot = self.constructFromPrePost(preorder[1:L+2], postorder[:L+1])\n",
    "        rightroot = self.constructFromPrePost(preorder[L+2:], postorder[L+1:-1])\n",
    "        #连接左右\n",
    "        root.left = leftroot\n",
    "        root.right = rightroot\n",
    "        return root\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:L + 1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L + 1:], postorder[L : -1])\n",
    "\n",
    "        return root\n",
    "        #不能取到-1，因为postorder[-1]是根结点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return node\n",
    "        idx = postorder.index(preorder[1])\n",
    "        node.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        node.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.val2Index = {}\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.val2Index[postorder[i]] = i\n",
    "        print(self.val2Index)\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder) - 1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        rootVal = preorder[preStart]\n",
    "        rootLeftVal = preorder[preStart + 1]\n",
    "        leftIndex = self.val2Index[rootLeftVal]\n",
    "        leftSize = leftIndex - postStart + 1\n",
    "        root = TreeNode(rootVal)\n",
    "        root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, leftIndex)\n",
    "        root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, leftIndex + 1, postEnd - 1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder: return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1: return root\n",
    "\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:L+1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L+1:], postorder[L:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.valToIndex = {}\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i in range(len(postorder)):\n",
    "            self.valToIndex[postorder[i]]=i\n",
    "        return self.build(preorder,0,len(preorder)-1,postorder,0,len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        \n",
    "        rootVal = preorder[preStart]\n",
    "        root = TreeNode(rootVal)\n",
    "        if preStart == preEnd:\n",
    "            return root\n",
    "        \n",
    "        # 后序序列中左子树的根节点的index\n",
    "        index = self.valToIndex[preorder[preStart+1]]\n",
    "        leftSize = index - postStart + 1\n",
    "        root.left = self.build(preorder, preStart+1, preStart + leftSize, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + leftSize+1, preEnd, postorder, index+1,postEnd-1)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.helper(preorder, postorder, 0, len(preorder)-1, 0, len(postorder)-1)\n",
    "    \n",
    "    def helper(self, preorder, postorder, pre_l, pre_h, post_l, post_h):\n",
    "        if pre_l > pre_h or post_l > post_h:\n",
    "            return None\n",
    "        \n",
    "        if pre_l == pre_h:\n",
    "            return TreeNode(preorder[pre_l])\n",
    "        \n",
    "        index = -1\n",
    "        for i in range(post_l, post_h+1):\n",
    "            if postorder[i] == preorder[pre_l+1]:\n",
    "                index = i\n",
    "        \n",
    "        root = TreeNode(preorder[pre_l])\n",
    "        length = index - post_l + 1\n",
    "        root.left = self.helper(preorder, postorder, pre_l+1, pre_l+length, post_l, index)\n",
    "        root.right = self.helper(preorder, postorder,  pre_l+length+1, pre_h, index+1, post_h-1)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "           \n",
    "        l = postorder.index(preorder[1]) + 1\n",
    "        root.left = self.constructFromPrePost(preorder[1:l+1], postorder[:l])\n",
    "        root.right = self.constructFromPrePost(preorder[l+1:],postorder[l:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left = preorder[1]\n",
    "        n = len(postorder)\n",
    "        for i in range(len(postorder)):\n",
    "            if postorder[i] == left:\n",
    "                postleft = postorder[0:i+1]\n",
    "                postright = postorder[i+1:n-1]\n",
    "                lenleft = len(postleft)\n",
    "                preleft = preorder [1:lenleft+1]\n",
    "                preright = preorder[lenleft+1:]\n",
    "                break\n",
    "        root.left = self.constructFromPrePost(preleft, postleft)\n",
    "        root.right = self.constructFromPrePost(preright, postright)\n",
    "        return root\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not len(preorder):\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        partition = postorder.index(preorder[1])\n",
    "        root.left = self.constructFromPrePost(preorder[1:1+partition+1], postorder[:partition])\n",
    "        root.right = self.constructFromPrePost(preorder[1+partition+1:], postorder[partition+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    " \n",
    "        if list1:\n",
    "            test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        if list2:\n",
    "            test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        \n",
    "        left_root = preorder[1]\n",
    "        left_root_post_index = postorder.index(left_root)\n",
    "        #左子树的nums的个数为（left_root_post_index+1）\n",
    "        root.left = self.constructFromPrePost(preorder[1:left_root_post_index+2],\n",
    "        postorder[:left_root_post_index + 1])\n",
    "        root.right = self.constructFromPrePost(preorder[left_root_post_index+2:],\n",
    "        postorder[left_root_post_index+1:])\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not postorder:\n",
    "            return None        \n",
    "        root = TreeNode(postorder[-1])#preorder[0]\n",
    "        if len(postorder) == 1:\n",
    "            return root \n",
    "\n",
    "        l_index = postorder.index(preorder[1])\n",
    "        # r_index = preorder.index(postorder[-2])\n",
    "        root.left = self.constructFromPrePost(preorder[1:l_index+2], postorder[:l_index+1])\n",
    "        root.right = self.constructFromPrePost(preorder[l_index+2:], postorder[l_index+1:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def createTree(preorder, postorder, n):\n",
    "            if n == 0:\n",
    "                return\n",
    "            node = TreeNode(preorder[0])\n",
    "            if n == 1:\n",
    "                return node\n",
    "            k = 0\n",
    "            # 对于后序序列，0~k是左子树，节点数目为k+1\n",
    "            while preorder[1] != postorder[k]:\n",
    "                k += 1\n",
    "            node.left = createTree(preorder[1:k + 2], postorder[:k + 1], k + 1)\n",
    "            node.right = createTree(preorder[k + 2:], postorder[k + 1:-1], n - k - 2)\n",
    "            return node\n",
    "        return createTree(preorder, postorder, len(preorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "        val_to_index = {}\n",
    "\n",
    "        for i in range(len(postorder)):\n",
    "            val_to_index[postorder[i]] = i\n",
    "\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(preorder)-1, val_to_index)\n",
    "        \n",
    "    \n",
    "    def build(self, preorder, pre_start, pre_end, postorder, post_start, post_end, val_to_index):\n",
    "\n",
    "        if pre_start > pre_end:\n",
    "            return\n",
    "\n",
    "        if pre_start == pre_end:\n",
    "            return TreeNode(preorder[pre_start])\n",
    "        \n",
    "        root_val = preorder[pre_start]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        left_root_val = preorder[pre_start+1]\n",
    "        left_root_idx = val_to_index[left_root_val]\n",
    "        left_num = left_root_idx - post_start + 1\n",
    "\n",
    "        root.left = self.build(preorder, pre_start+1, pre_start+left_num, postorder, post_start, left_root_idx-1, val_to_index)\n",
    "        root.right = self.build(preorder, pre_start+left_num+1, pre_end, postorder, left_root_idx+1, post_end, val_to_index)\n",
    "\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder)==0:\n",
    "            return None\n",
    "        root=TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        leftroot=preorder[1]\n",
    "        index=postorder.index(leftroot)\n",
    "        leftsize=index+1\n",
    "        root.left=self.constructFromPrePost(preorder[1:leftsize+1],postorder[:leftsize])\n",
    "        root.right=self.constructFromPrePost(preorder[leftsize+1:],postorder[leftsize:len(preorder)-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        idx = postorder.index(preorder[1])\n",
    "        root.left = self.constructFromPrePost(preorder[1:idx+2], postorder[:idx+1])\n",
    "        root.right = self.constructFromPrePost(preorder[idx+2:], postorder[idx+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0 or len(postorder) == 0:\n",
    "            return None \n",
    "          \n",
    "        root_val = preorder[0]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        if len(preorder) == 1:\n",
    "            postorder_left, postorder_right, preorder_left, preorder_right = [], [], [], []\n",
    "        else: \n",
    "            left_root_val = preorder[1]\n",
    "            left_root_idx_postorder = postorder.index(left_root_val)\n",
    "            \n",
    "            postorder_left = postorder[:left_root_idx_postorder+1]\n",
    "            postorder_right = postorder[left_root_idx_postorder+1:-1]\n",
    "            \n",
    "            preorder_left = preorder[1:len(postorder_left)+1]\n",
    "            preorder_right = preorder[len(postorder_left)+1:]\n",
    "        \n",
    "\n",
    "            # print(root_val, left_root_val, left_root_idx_postorder, preorder_left, preorder_right, postorder_left, postorder_right)\n",
    "\n",
    "\n",
    "        left = self.constructFromPrePost(preorder=preorder_left, postorder=postorder_left)\n",
    "        right = self.constructFromPrePost(preorder=preorder_right, postorder=postorder_right)\n",
    "\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        \n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        \n",
    "        k = 0\n",
    "        while preorder[1] != postorder[k]:\n",
    "            k += 1\n",
    "\n",
    "        node.left = self.constructFromPrePost(preorder[1: k+2], postorder[: k+1])\n",
    "        node.right = self.constructFromPrePost(preorder[k+2:], postorder[k+1: -1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(preorder,postorder):\n",
    "            if not preorder:\n",
    "                return\n",
    "            if len(preorder)==1:\n",
    "                return TreeNode(preorder[0])\n",
    "            # 找到根结点\n",
    "            root=TreeNode(preorder[0])\n",
    "            # 根据前序遍历序列第二个元素，确定后序遍历序列中左子树的范围\n",
    "            left_cnt=postorder.index(preorder[1])+1\n",
    "            root.left=dfs(preorder[1:1+left_cnt],postorder[:left_cnt])\n",
    "            root.right=dfs(preorder[left_cnt+1:],postorder[left_cnt:-1])\n",
    "            return root\n",
    "        return dfs(preorder,postorder)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def constructFromPrePost(self, pre, post):\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root_val = preorder[0]\n",
    "\n",
    "        l_preorder = preorder[1:postorder.index(preorder[1])+2]\n",
    "        r_preorder = preorder[postorder.index(preorder[1])+2:]\n",
    "        l_postorder = postorder[:len(l_preorder)]\n",
    "        r_postorder = postorder[len(l_preorder):-1]\n",
    "        root = TreeNode(root_val)\n",
    "        l = self.constructFromPrePost(l_preorder, l_postorder)\n",
    "        r = self.constructFromPrePost(r_preorder, r_postorder)\n",
    "\n",
    "        root.left = l\n",
    "        root.right = r\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "    \n",
    "    def build(self, preorder, pre_start, pre_end, postorder, pos_start, pos_end):\n",
    "        if pre_start > pre_end:\n",
    "            return None\n",
    "        \n",
    "        if pre_start == pre_end:\n",
    "            return TreeNode(preorder[pre_start])\n",
    "        \n",
    "        root_val = preorder[pre_start]\n",
    "        left_root_val = preorder[pre_start + 1]\n",
    "        left_index = postorder.index(left_root_val)\n",
    "        left_size = left_index - pos_start + 1\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        root.left = self.build(preorder, pre_start + 1, pre_start + left_size, postorder, pos_start, left_index)\n",
    "        root.right = self.build(preorder, pre_start + left_size + 1, pre_end, postorder, left_index + 1, pos_end - 1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        \n",
    "        node = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return node\n",
    "        \n",
    "        k = 0\n",
    "        while preorder[1] != postorder[k]:\n",
    "            k += 1\n",
    "\n",
    "        node.left = self.constructFromPrePost(preorder[1: k+2], postorder[: k+1]) # 注意k+2\n",
    "        node.right = self.constructFromPrePost(preorder[k+2:], postorder[k+1: -1])\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        rt = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return rt\n",
    "        t = preorder[1]\n",
    "        pt = postorder.index(t)\n",
    "        rt.left = self.constructFromPrePost(preorder[1:pt + 2], postorder[:pt + 1])\n",
    "        rt.right = self.constructFromPrePost(preorder[pt + 2:], postorder[pt + 1:-1])\n",
    "        return rt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    "\n",
    "        test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "\n",
    "        test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, pre: List[int], post: List[int]) -> Optional[TreeNode]:\n",
    "        if not pre: return None\n",
    "        root = TreeNode(pre[0])\n",
    "        if len(pre) == 1: return root\n",
    "\n",
    "        L = post.index(pre[1]) + 1\n",
    "        root.left = self.constructFromPrePost(pre[1:L+1], post[:L])\n",
    "        root.right = self.constructFromPrePost(pre[L+1:], post[L:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.postVal2Idx = {}\n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        root_val = preorder[preStart]\n",
    "        left_root_val = preorder[preStart+1]\n",
    "        index = self.postVal2Idx[left_root_val]\n",
    "        left_size = index - postStart + 1\n",
    "        root = TreeNode(root_val)\n",
    "        root.left = self.build(preorder, preStart+1, preStart + left_size, postorder, postStart, index)\n",
    "        root.right = self.build(preorder, preStart + left_size + 1, preEnd, postorder, index+1, postEnd-1)\n",
    "        return root\n",
    "        \n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        for i, val in enumerate(postorder):\n",
    "            self.postVal2Idx[val] = i\n",
    "        # for i in range(len(postorder)):\n",
    "        #     self.postVal2Idx[postorder[i]] = i\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def dfs(pre, post):\n",
    "            if not pre: \n",
    "                return None\n",
    "            root = TreeNode(pre[0])\n",
    "            if len(pre) == 1: \n",
    "                return root\n",
    "\n",
    "            L = post.index(pre[1]) + 1\n",
    "            root.left = dfs(pre[1:L+1], post[:L])\n",
    "            root.right = dfs(pre[L+1:], post[L:-1])\n",
    "            return root\n",
    "        return dfs(preorder, postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        #根据前序与后序的性质递归地连接\n",
    "        if not preorder:\n",
    "            return None\n",
    "        root=TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return root\n",
    "        j=postorder.index(preorder[1])\n",
    "        root.left=self.constructFromPrePost(preorder[1:j+2],postorder[:j+1])\n",
    "        root.right=self.constructFromPrePost(preorder[j+2:],postorder[j+1:-1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        root = TreeNode()\n",
    "        def dfs(preorder, postorder, root):\n",
    "            if not (preorder and postorder):\n",
    "                return\n",
    "            root.val = preorder[0]\n",
    "            if len(preorder) == 1:\n",
    "                return\n",
    "            left_root = preorder[1]\n",
    "            left_root_index = postorder.index(left_root)\n",
    "            \n",
    "            left_postorder = postorder[:-1][:left_root_index+1]\n",
    "            right_postorder = postorder[:-1][left_root_index+1:]\n",
    "\n",
    "            left_preorder = preorder[1:][:len(left_postorder)]\n",
    "            right_preorder = preorder[1:][len(left_postorder):]\n",
    "\n",
    "            if left_preorder:\n",
    "                root.left = TreeNode()\n",
    "                dfs(left_preorder, left_postorder, root.left)\n",
    "\n",
    "            if right_preorder:\n",
    "                root.right = TreeNode()\n",
    "                dfs(right_preorder, right_postorder, root.right)\n",
    "\n",
    "        dfs(preorder, postorder, root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        def tree(preorder, postorder):\n",
    "            if not preorder or not postorder:\n",
    "                return\n",
    "            root = TreeNode(preorder[0])\n",
    "            if len(preorder)>=2:\n",
    "                val = preorder[1]\n",
    "                idx = postorder.index(val)\n",
    "                l_pre = preorder[1:idx+2]\n",
    "                l_post = postorder[:idx+1]\n",
    "                r_pre = preorder[idx+2:]\n",
    "                r_post = postorder[idx+1:-1]\n",
    "                root.left = tree(l_pre, l_post)\n",
    "                root.right = tree(r_pre, r_post)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return tree(preorder, postorder)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(preorder) == 0:\n",
    "            return None\n",
    "        if len(preorder) == 1:\n",
    "            return TreeNode(preorder[0])\n",
    "        root = TreeNode(preorder[0])\n",
    "        left = preorder[1]\n",
    "        index = postorder.index(left)\n",
    "        root.left = self.constructFromPrePost(preorder[1:index + 2], postorder[:index + 1])\n",
    "        root.right = self.constructFromPrePost(preorder[index + 2:], postorder[index + 1:-1])\n",
    "        return root\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return\n",
    "        num = preorder[0]\n",
    "        root = TreeNode(num)\n",
    "        if len(preorder)>=2:\n",
    "            left_root = preorder[1]\n",
    "            index = postorder.index(left_root)\n",
    "            root.left = self.constructFromPrePost(preorder[1:index+2],postorder[:index+1])\n",
    "            root.right = self.constructFromPrePost(preorder[index+2:],postorder[index+1:-1])\n",
    "        return root\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        self.map = {num:i for i, num in enumerate(postorder)}\n",
    "\n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)\n",
    "\n",
    "    \n",
    "    def build(self, preorder, prestart, preend, inorder, instart, inend):\n",
    "        if prestart > preend:\n",
    "            return None\n",
    "        if prestart == preend:\n",
    "            return TreeNode(preorder[prestart]) \n",
    "\n",
    "        root_val = preorder[prestart]\n",
    "        root = TreeNode(root_val) \n",
    "         \n",
    "        next_root_val = preorder[prestart+1]\n",
    "        index = self.map[next_root_val]\n",
    "        size = index - instart + 1\n",
    "        root.left = self.build(preorder, prestart+1, prestart+size, inorder, instart, index)\n",
    "        root.right = self.build(preorder, prestart+size+1, preend, inorder, index+1, inend-1)\n",
    "\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-172f0/\n",
    "# 二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。\n",
    "# 之前都有中序遍历，所以靠中序的root的index。这道题没有中序，所以就靠前序的第一个left_val,再去后序找left_index\n",
    "# 前序+后序：没有唯一答案\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "        # if len(preorder) == 1 or len(postorder) == 1: # 不能写在这，只能写在下面那个函数里\n",
    "        #     return TreeNode(preorder[0])\n",
    "\n",
    "        pre_s = 0\n",
    "        pre_e = len(preorder) - 1\n",
    "        post_s = 0\n",
    "        post_e = len(postorder) - 1\n",
    "\n",
    "        return self.build(preorder, pre_s, pre_e, postorder, post_s, post_e)\n",
    "\n",
    "    def build(self, preorder, pre_s, pre_e, postorder, post_s, post_e):\n",
    "        if pre_s > pre_e:\n",
    "            return None\n",
    "\n",
    "        # 重点，意思就是只有一个数字,只能写在这，因为循环到最后可能两者也会相等\n",
    "        # 必须写在这，否则后面preorder[pre_s + 1]可能会溢出边界\n",
    "        if pre_s == pre_e:\n",
    "            return TreeNode(preorder[pre_s])\n",
    "        \n",
    "        root_val = preorder[pre_s]\n",
    "        root = TreeNode(root_val)\n",
    "\n",
    "        left_val = preorder[pre_s + 1]\n",
    "        left_index = postorder.index(left_val)\n",
    "        leftsize = left_index - post_s + 1\n",
    "        # 这里加1也是重点。把后序的图画出来，如post_s = 0,left_index=5,说明左子树有0 1 2 3 4 5，一共6个数，但是5-0=5，所以要加1\n",
    "\n",
    "        # 递归构造左右子树\n",
    "        root.left = self.build(preorder, pre_s + 1, pre_s + 1 + leftsize - 1, postorder, post_s, left_index)\n",
    "        root.right = self.build(preorder, pre_s + leftsize + 1, pre_e, postorder, left_index + 1, post_e - 1)\n",
    "\n",
    "        return root\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         # 存储 postorder 中值到索引的映射\n",
    "#         self.valToIndex = {}\n",
    "\n",
    "#     def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:\n",
    "#         for i in range(len(postorder)):\n",
    "#             self.valToIndex[postorder[i]] = i\n",
    "#         return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)\n",
    "\n",
    "#     # 根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd] 构建二叉树，并返回根节点。\n",
    "#     def build(self, preorder: List[int], preStart: int, preEnd: int, postorder: List[int], postStart: int, postEnd: int) -> TreeNode:\n",
    "#         if preStart > preEnd:\n",
    "#             return None\n",
    "#         if preStart == preEnd:\n",
    "#             return TreeNode(preorder[preStart])\n",
    "\n",
    "#         # root 节点对应的值就是前序遍历数组的第一个元素\n",
    "#         rootVal = preorder[preStart]\n",
    "#         # root.left 的值是前序遍历第二个元素\n",
    "#         # 通过前序和后序遍历构造二叉树的关键在于通过左子树的根节点\n",
    "#         # 确定 preorder 和 postorder 中左右子树的元素区间\n",
    "#         leftRootVal = preorder[preStart + 1]\n",
    "#         # leftRootVal 在后序遍历数组中的索引\n",
    "#         index = self.valToIndex[leftRootVal]\n",
    "#         # 左子树的元素个数\n",
    "#         leftSize = index - postStart + 1\n",
    "\n",
    "#         # 先构造出当前根节点\n",
    "#         root = TreeNode(rootVal)\n",
    "#         # 递归构造左右子树\n",
    "#         # 根据左子树的根节点索引和元素个数推导左右子树的索引边界\n",
    "#         root.left = self.build(preorder, preStart + 1, preStart + leftSize, postorder, postStart, index)\n",
    "#         root.right = self.build(preorder, preStart + leftSize + 1, preEnd, postorder, index + 1, postEnd - 1)\n",
    "\n",
    "#         return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        if len(preorder) == 1:  # 数组长度为1时, 直接返回即可\n",
    "            return TreeNode(preorder[0])\n",
    "            \n",
    "        root = TreeNode(preorder[0])  # 根据前序数组的第1个元素, 创建根节点\n",
    "        left_count = postorder.index(preorder[1]) + 1  # 根据前序数组的第2个元素确定后序数组的左子树范围（左子树的节点个数）\n",
    "        \n",
    "        # 递归执行前序数组左边、后序数组左边。前序数组右边，后序数组右边\n",
    "        root.left = self.constructFromPrePost(preorder[1: left_count+1], postorder[: left_count])\n",
    "        root.right = self.constructFromPrePost(preorder[left_count+1:], postorder[left_count: -1])\n",
    "        \n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def sub(pre, prestart, preend, post, poststart, postend):\n",
    "            if prestart > preend:\n",
    "                return None\n",
    "            if prestart == preend:\n",
    "                return TreeNode(pre[prestart])\n",
    "            root = TreeNode(pre[prestart])\n",
    "            index = post.index(pre[prestart + 1])\n",
    "            left_size = index - poststart + 1\n",
    "            root.left = sub(pre, prestart + 1, prestart + left_size, post, poststart, index - 1)\n",
    "            root.right = sub(pre, prestart + left_size + 1, preend, post, index + 1, postend)\n",
    "            return root\n",
    "        return sub(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        if not preorder:\n",
    "            return None\n",
    "        test_tree=TreeNode(preorder[0])      \n",
    "        if len(preorder)==1:\n",
    "            return test_tree\n",
    "        \n",
    "        ind1=postorder.index(preorder[1])\n",
    "                                                           \n",
    "        list1=postorder[0:ind1+1]\n",
    "        list3=preorder[1:ind1+2]\n",
    "\n",
    "        list2=preorder[ind1+2:]\n",
    "        list4=postorder[ind1+1:-1]\n",
    "\n",
    "        # test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        # test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "        if list1:\n",
    "            test_tree.left=self.constructFromPrePost(list3,list1)\n",
    "        if list2:\n",
    "            test_tree.right=self.constructFromPrePost(list2,list4)\n",
    "\n",
    "        return test_tree\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if len(postorder)==0:\n",
    "            return\n",
    "        if len(postorder)==1:\n",
    "            return TreeNode(postorder[0])\n",
    "        idx=postorder.index(preorder[1])\n",
    "        return TreeNode(postorder[-1],self.constructFromPrePost(preorder[1:2+idx],postorder[:idx+1]),self.constructFromPrePost(preorder[2+idx:],postorder[idx+1:-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def helpConstruct(preorder, prelow, prehigh, postorder,postlow, posthigh):\n",
    "            if prelow < 0 or postlow < 0 or prehigh >= len(preorder) or posthigh >= len(postorder) or prelow > prehigh or postlow > posthigh:\n",
    "                return None\n",
    "\n",
    "            rootVal = preorder[prelow]\n",
    "            root = TreeNode(rootVal)\n",
    "            \n",
    "            if prelow + 1 > prehigh:\n",
    "                return root\n",
    "            leftRootVal = preorder[prelow+1]\n",
    "            # 在 postorder 中找 leftRootVal 所在的索引\n",
    "            leftRootPostIndex = postlow\n",
    "            for i in range(postlow, posthigh+1):\n",
    "                if postorder[i] == leftRootVal:\n",
    "                    leftRootPostIndex = i\n",
    "            \n",
    "            leftSize = leftRootPostIndex - postlow + 1\n",
    "\n",
    "            # 构造左子树和右子树\n",
    "            root.left = helpConstruct(preorder, prelow+1, prelow + leftSize, postorder, postlow, leftRootPostIndex)\n",
    "            root.right = helpConstruct(preorder, prelow + leftSize+1, prehigh, postorder,leftRootPostIndex+1, posthigh-1)\n",
    "\n",
    "            return root\n",
    "\n",
    "        return helpConstruct(preorder,0,len(preorder)-1,postorder,0, len(postorder)-1)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def construct(preorder, postorder):\n",
    "            if len(preorder) == 0:\n",
    "                return\n",
    "            if len(preorder) == 1:\n",
    "                return TreeNode(preorder[0])\n",
    "            root_val = preorder[0]\n",
    "            left_root = preorder[1]\n",
    "            left_idx = postorder.index(left_root)\n",
    "            left_postorder = postorder[:left_idx+1]\n",
    "            right_postorder = postorder[left_idx+1:-1]\n",
    "\n",
    "            right_root = postorder[-2]\n",
    "            if right_root==left_root:\n",
    "                right_postorder=right_preorder=[]\n",
    "                left_preorder=preorder[1:]\n",
    "            else:\n",
    "                right_idx = preorder.index(right_root)\n",
    "                left_preorder = preorder[1:right_idx]\n",
    "                right_preorder = preorder[right_idx:]\n",
    "            return TreeNode(\n",
    "                root_val,\n",
    "                construct(left_preorder, left_postorder),\n",
    "                construct(right_preorder, right_postorder)\n",
    "            )\n",
    "        return construct(preorder, postorder)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder or not postorder:\n",
    "            return None\n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        index_left = postorder.index(preorder[1])\n",
    "        if len(preorder) > index_left + 2:\n",
    "            index_right = preorder.index(postorder[-2])\n",
    "\n",
    "            root.left = self.constructFromPrePost(preorder[1:index_right], postorder[:index_left + 1])\n",
    "            root.right = self.constructFromPrePost(preorder[index_right:], postorder[index_left + 1 : -1])\n",
    "        else:\n",
    "            root.left = self.constructFromPrePost(preorder[1:], postorder[:index_left + 1])\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        def make(i,j,k):\r\n",
    "            if k==0:\r\n",
    "                return None\r\n",
    "            root=TreeNode(preorder[i])\r\n",
    "            if k==1:\r\n",
    "                return root\r\n",
    "            kk=postorder.index(preorder[i+1],j)-j+1\r\n",
    "            root.left=make(i+1,j,kk)\r\n",
    "            root.right=make(i+1+kk,j+kk,k-kk-1)\r\n",
    "            return root\r\n",
    "\r\n",
    "        return make(0,0,len(preorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\r\n",
    "        if not preorder:\r\n",
    "            return None\r\n",
    "        parent=TreeNode(preorder[0])\r\n",
    "        if len(preorder)==1:\r\n",
    "            return parent\r\n",
    "        L=postorder.index(preorder[1])+1\r\n",
    "        parent.left=self.constructFromPrePost(preorder[1:L+1],postorder[:L])\r\n",
    "        parent.right=self.constructFromPrePost(preorder[L+1:],postorder[L:-1])\r\n",
    "        return parent\r\n",
    "    \r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        \n",
    "        root = TreeNode(preorder[0])\n",
    "        if len(preorder) == 1:\n",
    "            return root\n",
    "        \n",
    "        # postorder中左子树根出现在左子树节点最后\n",
    "        # 根据index可以确定左子树长度L\n",
    "        L = postorder.index(preorder[1]) + 1\n",
    "\n",
    "        root.left = self.constructFromPrePost(preorder[1:L+1], postorder[:L])\n",
    "        root.right = self.constructFromPrePost(preorder[L+1:], postorder[L:-1])\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "\n",
    "        root = TreeNode(preorder[0])\n",
    "        \n",
    "        if len(preorder) ==1:\n",
    "            return root\n",
    "        left_root_index = postorder.index(preorder[1])\n",
    "\n",
    "        left_preorder = preorder[1: 2+ left_root_index]\n",
    "        left_postorder = postorder[:left_root_index + 1]\n",
    "        right_preorder = preorder[2+ left_root_index:]\n",
    "        right_postorder = postorder[left_root_index + 1: -1]\n",
    "\n",
    "        root.left = self.constructFromPrePost(left_preorder, left_postorder)\n",
    "        root.right = self.constructFromPrePost(right_preorder, right_postorder)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        if not preorder:\n",
    "            return None\n",
    "        tree = TreeNode(preorder[0])\n",
    "        if len(preorder)==1:\n",
    "            return tree\n",
    "        i = postorder.index(preorder[1])\n",
    "        left_pre = preorder[1:i+2]\n",
    "        left_post = postorder[:i+1]\n",
    "        right_pre = preorder[i+2:]\n",
    "        right_post = postorder[i+1:-1]\n",
    "        print(left_pre,left_post,right_pre,right_post)\n",
    "        tree.left = self.constructFromPrePost(left_pre,left_post)\n",
    "        tree.right = self.constructFromPrePost(right_pre,right_post)\n",
    "        return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        dic = {}\n",
    "        for i, ele in enumerate(postorder):\n",
    "            dic[ele] = i\n",
    "        def judge(pre_begin, pre_end, post_begin, post_end):\n",
    "            if pre_begin > pre_end:\n",
    "                return\n",
    "            if pre_begin == pre_end:\n",
    "                return TreeNode(preorder[pre_begin])\n",
    "\n",
    "            root = TreeNode(preorder[pre_begin])\n",
    "            first_left = preorder[pre_begin + 1]\n",
    "            ind = dic[first_left]\n",
    "            root.left = judge(pre_begin + 1, pre_begin + ind - post_begin + 1, post_begin, ind)\n",
    "            root.right = judge(pre_begin + ind - post_begin + 2, pre_end, ind + 1, post_end - 1)\n",
    "            return root\n",
    "        return judge(0, len(preorder) - 1, 0, len(postorder) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def constructFromPrePost(self, pre, post):\n",
    "        post_map = dict()\n",
    "        for i,val in enumerate(post):\n",
    "            post_map[val] = i\n",
    "        def make(i0, i1, N):\n",
    "            if N == 0: return None\n",
    "            root = TreeNode(pre[i0])\n",
    "            if N == 1: return root\n",
    "\n",
    "            L = post_map[pre[i0+1]] + 1 - i1\n",
    "\n",
    "            root.left = make(i0 + 1, i1, L)\n",
    "            root.right = make(i0 + L + 1, i1 + L, N - 1 - L)\n",
    "            return root\n",
    "\n",
    "        return make(0, 0, len(pre))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def createTree(preorder, postorder, n):\n",
    "            if n == 0:\n",
    "                return None\n",
    "\n",
    "            node = TreeNode(preorder[0])\n",
    "            if n == 1:\n",
    "                return node\n",
    "            \n",
    "            k = 0\n",
    "            while preorder[1] != postorder[k]:\n",
    "                k += 1\n",
    "            \n",
    "            node.left = createTree(preorder[1:k+2], postorder[:k+1], k+1)  # 左子树长度为 k+1\n",
    "            node.right = createTree(preorder[k+2:], postorder[k+1:n-2], n-k-2)\n",
    "            return node\n",
    "        return createTree(preorder, postorder, len(preorder))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "\n",
    "        val2idx_post = {val:idx for idx, val in enumerate(postorder)}\n",
    "\n",
    "        def _construct(pre_start, pre_end, post_start, post_end):\n",
    "            if pre_start == pre_end:\n",
    "                return None\n",
    "\n",
    "            root_val = preorder[pre_start]\n",
    "            if pre_start == pre_end - 1:\n",
    "                return TreeNode(root_val)\n",
    "\n",
    "            post_idx = val2idx_post[preorder[pre_start + 1]]\n",
    "            left_len = post_idx - post_start + 1\n",
    "\n",
    "            left = _construct(pre_start + 1, pre_start + left_len + 1,\n",
    "                                post_start, post_start + left_len + 1)\n",
    "            right = _construct(pre_start + left_len + 1, pre_end,\n",
    "                                post_idx + 1, post_end - 1)\n",
    "            return TreeNode(root_val, left, right)\n",
    "\n",
    "        return _construct(0, len(preorder), 0, len(postorder))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # x [l] [r]\n",
    "        # [l] [r] x\n",
    "\n",
    "        # x [l ...] [r ... ]\n",
    "        # [... l]   [.... r] x\n",
    "\n",
    "        map = dict()\n",
    "        for i, x in enumerate(preorder):\n",
    "            map[x] = i\n",
    "\n",
    "        n = len(preorder)\n",
    "        def dfs(i,j, a,b) -> Optional[TreeNode]:\n",
    "            if i > j or a > b:\n",
    "                return None  \n",
    "\n",
    "            root = preorder[i]\n",
    "            if j-i+1 == 1:\n",
    "                return TreeNode(root, None, None)\n",
    "            \n",
    "\n",
    "            # x [l, ] [r   ]\n",
    "            # [   l] [  r] x\n",
    "            y = map[postorder[b-1]] \n",
    "            t = y - i - 1 #要求>0\n",
    "            \n",
    "            \n",
    "            \n",
    "            # [x, j] [a+l, b]\n",
    "            left = dfs(i+1, y-1, a, a+t-1) \n",
    "            right = dfs(y, j, a+t, b-1)\n",
    "            return TreeNode(root, left, right)\n",
    "        return dfs(0, n-1, 0, n-1)\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # def createTree(preorder, postorder, n):\n",
    "        #     if n == 0:\n",
    "        #         return\n",
    "        #     node = TreeNode(preorder[0])\n",
    "        #     if n == 1:\n",
    "        #         return node\n",
    "        #     k = 0\n",
    "        #     # 对于后序序列，0~k是左子树，节点数目为k+1\n",
    "        #     while preorder[1] != postorder[k]:\n",
    "        #         k += 1\n",
    "        #     node.left = createTree(preorder[1:k + 2], postorder[:k + 1], k + 1)\n",
    "        #     node.right = createTree(preorder[k + 2:], postorder[k + 1:-1], n - k - 2)\n",
    "        #     return node\n",
    "        # return createTree(preorder, postorder, len(preorder))\n",
    "\n",
    "        # def recur(root, left, right):\n",
    "        #     if left > right: return \n",
    "        #     node = TreeNode(preorder[root])\n",
    "        #     if root == len(preorder) - 1:\n",
    "        #         return node\n",
    "        #     i = dic[preorder[root + 1]]\n",
    "        #     if left <= i <= right:\n",
    "        #         node.left = recur(root + 1, left, i)\n",
    "        #         node.right = recur(root + i - left + 2, i + 1, right - 1)\n",
    "        #     return node\n",
    "        # dic, preorder = {}, preorder\n",
    "        # for i in range(len(postorder)):\n",
    "        #     dic[postorder[i]] = i\n",
    "        # return recur(0, 0, len(postorder) - 1)\n",
    "\n",
    "        def recur(root, left, right):\n",
    "            if left > right: return\n",
    "            node = TreeNode(preorder[root])\n",
    "            if root == len(preorder) - 1: return node\n",
    "            i = dic[preorder[root + 1]]\n",
    "            if left <= i <= right:\n",
    "                node.left = recur(root + 1, left, i)\n",
    "                node.right = recur(root + i - left + 2, i + 1, right - 1)\n",
    "            return node\n",
    "        dic, preorder = {}, preorder\n",
    "        for i in range(len(postorder)):\n",
    "            dic[postorder[i]] = i\n",
    "        return recur(0, 0, len(postorder) - 1)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        # 构造hash查找index\n",
    "        self.postorderDict = {}\n",
    "\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        # 构造hash\n",
    "        for i in range(len(postorder)):\n",
    "            self.postorderDict[postorder[i]] = i\n",
    "        \n",
    "        return self.build(preorder, 0, len(preorder)-1, postorder, 0, len(postorder)-1)\n",
    "    \n",
    "    def build(self, preorder, preStart, preEnd, postorder, postStart, postEnd):\n",
    "        # 构造辅助递归函数build\n",
    "        # base case\n",
    "        if preStart > preEnd:\n",
    "            return None\n",
    "        if preStart == preEnd:\n",
    "            return TreeNode(preorder[preStart])\n",
    "        # 构造根节点\n",
    "        rootValue = preorder[preStart]\n",
    "        rootLeftValue = preorder[preStart+1]\n",
    "        root = TreeNode(rootValue)\n",
    "        # 查找左子树的root值\n",
    "        print(preStart, preEnd, len(preorder))\n",
    "        \n",
    "        # 在postorder中查询左子树root值的索引\n",
    "        index = self.postorderDict[rootLeftValue]\n",
    "        # 左子树的长度\n",
    "        leftRootLength = index - postStart + 1\n",
    "        # 递归构造左子树\n",
    "        root.left = self.build(preorder, preStart+1, preStart+leftRootLength, postorder, postStart, index)\n",
    "        # 递归构造右子树\n",
    "        root.right = self.build(preorder, preStart+leftRootLength+1, preEnd, postorder, index+1, postEnd-1)\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(pre,post):\n",
    "            if len(pre)==0:\n",
    "                return None\n",
    "            if len(pre)==1:\n",
    "                return TreeNode(pre[0])\n",
    "            rootVal=pre[0]\n",
    "            leftRootVal=pre[1]\n",
    "            leftLength=post.index(leftRootVal)+1\n",
    "            leftPre=pre[1:leftLength+1]\n",
    "            rightPre=pre[leftLength+1:]\n",
    "\n",
    "            leftPost=post[0:leftLength]\n",
    "            rightPost=post[leftLength:len(post)-1]\n",
    "            midNode=TreeNode(rootVal)\n",
    "            leftNode=build(leftPre,leftPost)\n",
    "            rightNode=build(rightPre,rightPost)\n",
    "            midNode.left=leftNode\n",
    "            midNode.right=rightNode\n",
    "            return midNode\n",
    "        return build(preorder,postorder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        def build(preStart, preEnd, postStart, postEnd):\n",
    "            if preStart > preEnd:\n",
    "                return None\n",
    "            elif preStart == preEnd:\n",
    "                return TreeNode(preorder[preStart])\n",
    "            \n",
    "            root = TreeNode(preorder[preStart])\n",
    "            leftroot_val = preorder[preStart + 1]\n",
    "            index = value2index[leftroot_val]\n",
    "            leftsize = index - postStart + 1\n",
    "            root.left = build(preStart + 1, preStart + leftsize, postStart, index)\n",
    "            root.right = build(preStart + leftsize + 1, preEnd, index + 1, postEnd)\n",
    "            return root\n",
    "        \n",
    "        value2index = dict()\n",
    "        for i in range(len(postorder)):\n",
    "            value2index[postorder[i]] = i\n",
    "        return build(0, len(preorder) - 1, 0, len(postorder) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:\n",
    "        hash_table = {val: i for i, val in enumerate(postorder)}\n",
    "\n",
    "        def build(pre_left: int, pre_right: int, post_left: int, post_right: int) -> Optional[TreeNode]:\n",
    "            if pre_left > pre_right:\n",
    "                return\n",
    "            root = TreeNode(val=preorder[pre_left])\n",
    "            # 不能省！！！因为左子节点不一定存在！！\n",
    "            if pre_left == pre_right:\n",
    "                return root\n",
    "            left_val = preorder[pre_left + 1]\n",
    "            post_left_pos = hash_table[left_val]\n",
    "            left_sublen = post_left_pos - post_left + 1\n",
    "\n",
    "            root.left = build(pre_left + 1, pre_left + left_sublen, post_left, post_left_pos)\n",
    "            root.right = build(pre_left + left_sublen + 1, pre_right, post_left_pos + 1, post_right - 1)\n",
    "\n",
    "            return root\n",
    "\n",
    "        ln = len(preorder)\n",
    "        return build(0, ln - 1, 0, ln - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prod = 1\n",
    "        M = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        \n",
    "        prefix = [1]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            prod = (prefix[-1] * grid[i][j]) % M\n",
    "            prefix.append(prod)\n",
    "\n",
    "        suffix = [1]\n",
    "        for i, j in product(reversed(range(m)), reversed(range(n))):\n",
    "            prod = (suffix[-1] * grid[i][j]) % M\n",
    "            suffix.append(prod)\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            idx = i * n + j\n",
    "            ans[i][j] = (prefix[idx] * suffix[m*n-1-idx]) % M\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        \n",
    "        s = [i for j in grid for i in j][::-1]\n",
    "        f = [1] * (m*n)\n",
    "        res = 1\n",
    "        for i,x in enumerate(s):\n",
    "            f[i] = res % 12345\n",
    "            res = (res*x) % 12345\n",
    "        f = f[::-1]\n",
    "        # print(s, f)\n",
    "        t = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp = grid[i][j]\n",
    "                grid[i][j] = (f[i*m+j] * t) % 12345\n",
    "                t = (t * temp) % 12345\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIV = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef mul(self, a, b):\n",
    "\t\treturn a * (b % DIV) % DIV\n",
    "\n",
    "\tdef constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\t\tn = len(grid)\n",
    "\t\tm = len(grid[0])\n",
    "\t\tflat = []\n",
    "\t\tfor i in grid:\n",
    "\t\t\tflat.extend(i)\n",
    "\n",
    "\t\tret = grid.copy()\n",
    "\t\t# 顺序遍历\n",
    "\t\tseq = [1]\n",
    "\t\tprod = 1\n",
    "\t\tfor i in range(len(flat) - 1):\n",
    "\t\t\tprod = self.mul(prod, flat[i])\n",
    "\t\t\tseq.append(prod)\n",
    "\t\t# 逆序遍历\n",
    "\t\trev = [1]\n",
    "\t\tprod = 1\n",
    "\t\tfor i in range(len(flat) - 1, 0, -1):\n",
    "\t\t\tprod = self.mul(prod, flat[i])\n",
    "\t\t\trev.append(prod)\n",
    "\t\tind = 0\n",
    "\t\tind_rev = -1\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tfor j in range(m):\n",
    "\t\t\t\tret[i][j] = self.mul(seq[ind], rev[ind_rev])\n",
    "\t\t\t\tind += 1\n",
    "\t\t\t\tind_rev -= 1\n",
    "\t\treturn ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict, deque\n",
    "from sortedcontainers import SortedList\n",
    "from functools import lru_cache\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        tt = 1\n",
    "        cnt1 = 0\n",
    "        m1 = {}\n",
    "        has = False\n",
    "        cntx = 0\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 % 12345 == 0:\n",
    "\n",
    "                    has = True\n",
    "                    rm = v2 // 12345\n",
    "                    cnt1 += rm\n",
    "                    m1[(k,k2)] = rm\n",
    "                    cntx += 1\n",
    "                else:\n",
    "                    tt *= v2\n",
    "\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if (k,k2) in m1:\n",
    "                    if cntx == 1:\n",
    "                        grid[k][k2] = ((cnt1-m1[(k,k2)]) +  tt) % 12345\n",
    "                    else:\n",
    "                        grid[k][k2] = 0\n",
    "                else:\n",
    "                    if has:\n",
    "                        grid[k][k2] = 0\n",
    "                    else:\n",
    "                        grid[k][k2] = tt // v2  % 12345\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        MOD = 12345\n",
    "        g = [grid[i][j] % MOD for i in range(m) for j in range(n)]\n",
    "        # print(g)\n",
    "        left, right = [1] * (m * n), [1] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                left[i * n + j] = 1 if not i and not j else (left[i * n + j - 1] * g[i * n + j - 1]) % MOD\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                right[i * n + j] = 1 if i == m - 1 and j == n - 1 else (right[i * n + j + 1] * g[i * n + j + 1]) % MOD\n",
    "        # print(left)\n",
    "        # print(right)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j] = left[i * n + j] * right[i * n + j] % MOD\n",
    "        return grid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        mul = 1\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] % MOD == 0:\n",
    "                    cnt += 1\n",
    "                if cnt == 2:\n",
    "                    flag = True\n",
    "                    break\n",
    "                mul *= grid[i][j]\n",
    "            if flag == True:\n",
    "                break\n",
    "        if flag == True:\n",
    "            return [[0] * m] * n\n",
    "        \n",
    "        res = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res[i][j] = (mul // grid[i][j]) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        mul = 1\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        cnt = 0\n",
    "        \n",
    "        flag = False\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] % MOD == 0:\n",
    "                    cnt += 1\n",
    "                if cnt == 2:\n",
    "                    flag = True\n",
    "                    break\n",
    "                mul *= grid[i][j]\n",
    "            if flag == True:\n",
    "                break\n",
    "        if flag == True:\n",
    "            return [[0] * m] * n\n",
    "        \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            tmp = []\n",
    "            for j in range(m):\n",
    "                tmp.append((mul // grid[i][j]) % MOD)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        # 前后缀分解\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        p = [[0] * m for _ in range(n)]\n",
    "        suffix = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                p[i][j] = suffix\n",
    "                suffix = suffix * grid[i][j] % 12345\n",
    "        prefix = 1\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, x in enumerate(line):\n",
    "                p[i][j] = p[i][j] * prefix % 12345\n",
    "                prefix = prefix * x % 12345\n",
    "        return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        count12345 = 0\n",
    "        accumulated = 1\n",
    "        for line in grid:\n",
    "            for x in line:\n",
    "                if x % 12345 == 0:\n",
    "                    count12345 += 1\n",
    "                    if count12345 > 1:\n",
    "                        return [[0] * m for _ in range(n)]\n",
    "                else:\n",
    "                    accumulated = accumulated * x\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, x in enumerate(line):\n",
    "                if count12345 == 0:\n",
    "                    grid[i][j] = (accumulated // x) % 12345\n",
    "                elif x % 12345 == 0:\n",
    "                    grid[i][j] = accumulated % 12345\n",
    "                else:\n",
    "                    grid[i][j] = 0\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prefix=[1]\n",
    "        row=len(grid)\n",
    "        col=len(grid[0])\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                prefix.append(prefix[-1]*grid[r][c]%12345)\n",
    "        n=row*col\n",
    "        suffix=[1]\n",
    "        for r in range(row-1,-1,-1):\n",
    "            for c in range(col-1,-1,-1):\n",
    "                suffix.append(suffix[-1]*grid[r][c]%12345)\n",
    "        suffix=suffix[::-1]\n",
    "        ans=[[0]*col for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                cur=i*col+j\n",
    "                ans[i][j]=prefix[cur]*suffix[cur+1]%12345\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        mod = 12345\n",
    "        cur = 1 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = cur \n",
    "                cur *= grid[i][j]\n",
    "                cur %= mod \n",
    "                \n",
    "        cur = 1\n",
    "        for i in range(m - 1, - 1, - 1):\n",
    "            for j in range(n - 1, - 1, - 1):\n",
    "                res[i][j] = res[i][j] * cur % mod \n",
    "                cur *= grid[i][j]\n",
    "                cur %= mod \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        # 左上，右下，蛇型模拟\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [[1 for i in range(m)] for j in range(n)]\n",
    "        mn = m * n\n",
    "        left = [1 for i in range(mn)]\n",
    "        right = [1 for i in range(mn)]\n",
    "        MOD = 12345\n",
    "        temp = 1\n",
    "        pos = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                temp = (temp * grid[i][j]) % MOD\n",
    "                left[pos] = temp\n",
    "                pos = pos + 1\n",
    "        temp = 1\n",
    "        pos = m * n - 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                temp = (temp * grid[i][j]) % MOD\n",
    "                right[pos] = temp\n",
    "                pos = pos - 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pos = i * m + j\n",
    "                if pos == 0:\n",
    "                    ans[i][j] = right[1]\n",
    "                elif pos == m * n - 1:\n",
    "                    ans[i][j] = left[-2]\n",
    "                else:\n",
    "                    ans[i][j] = (left[pos - 1] * right[pos + 1]) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"Created: 2023/10/15\"\"\"\n",
    "from typing import List, Dict\n",
    "\n",
    "Mod = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        big_table = []\n",
    "        table = [1] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                big_table.append(grid[i][j])\n",
    "\n",
    "        def f(i, j):\n",
    "            if i == j:\n",
    "                return big_table[i] % Mod\n",
    "            mid = (i+j) // 2\n",
    "            left = f(i, mid)\n",
    "            right = f(mid+1, j)\n",
    "            for i in range(i, mid+1):\n",
    "                table[i] = table[i] * right % Mod\n",
    "            for i in range(mid+1, j+1):\n",
    "                table[i] = table[i] * left % Mod\n",
    "            return left * right % Mod\n",
    "        f(0, m*n-1)\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                tmp.append(table[i*n+j])\n",
    "            ans.append(tmp)\n",
    "        return ans\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    s.constructProductMatrix([[1,2],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 12345\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        ans = [[1] * m for _ in range(n)]\n",
    "        tot = [1] * n\n",
    "        for i in range(n):\n",
    "            pref = [1] * (m + 1)\n",
    "            suff = [1] * (m + 1)\n",
    "            res = 1\n",
    "            for j in range(m):\n",
    "                res *= grid[i][j]\n",
    "                res %= mod\n",
    "                pref[j+1] = pref[j] * grid[i][j] % mod\n",
    "            for j in range(m-1, -1, -1):\n",
    "                suff[j] = suff[j+1] * grid[i][j] % mod\n",
    "            for j in range(m):\n",
    "                ans[i][j] = pref[j] * suff[j+1] % mod\n",
    "            tot[i] = res\n",
    "        pref = [1] * (n + 1)\n",
    "        suff = [1] * (n + 1)\n",
    "        for j in range(n):\n",
    "            pref[j+1] = pref[j] * tot[j] % mod\n",
    "        for j in range(n-1, -1, -1):\n",
    "            suff[j] = suff[j+1] * tot[j] % mod\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans[i][j] *= pref[i] * suff[i+1]\n",
    "                ans[i][j] %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n,m=len(grid),len(grid[0])\n",
    "        snt1,snt2,snt3,mul=0,0,0,1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                cnt1,cnt2,cnt3=0,0,0\n",
    "                while(grid[i][j]%3==0):grid[i][j]//=3;cnt1+=1\n",
    "                while(grid[i][j]%5==0):grid[i][j]//=5;cnt2+=1\n",
    "                while(grid[i][j]%823==0):grid[i][j]//=823;cnt3+=1\n",
    "                snt1,snt2,snt3=snt1+cnt1,snt2+cnt2,snt3+cnt3\n",
    "                mul=mul*grid[i][j]%12345\n",
    "                grid[i][j]=[cnt1,cnt2,cnt3,grid[i][j]]\n",
    "        print(grid)\n",
    "        def ksm(u,v):\n",
    "            res=1\n",
    "            while(v):\n",
    "                if(v&1):res=res*u%12345\n",
    "                u=u*u%12345;v>>=1\n",
    "            return res\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if(snt1-grid[i][j][0]>0 and snt2-grid[i][j][1]>0 and snt3-grid[i][j][2]>0):grid[i][j]=0\n",
    "                else:grid[i][j]=mul*ksm(grid[i][j][3],6575)*ksm(3,snt1-grid[i][j][0])*ksm(5,snt2-grid[i][j][1])*ksm(823,snt3-grid[i][j][2])%12345\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 12345\n",
    "        l = m * n\n",
    "        grid1 = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid1.append(grid[i][j] % mod)\n",
    "        grid = grid1\n",
    "        pre = [1]\n",
    "        tail = [1]\n",
    "        for i in range(l):\n",
    "            pre.append(pre[-1] * grid[i] % mod)\n",
    "            i = l - i - 1\n",
    "            tail.append(tail[-1] * grid[i] % mod)\n",
    "        tail = tail[::-1]\n",
    "        res = [[1 for i in range(n)] for j in range(m)]\n",
    "        for i in range(l):\n",
    "            res[i // n][i % n] = pre[i] * tail[i + 1] % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, a: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(a), len(a[0])\n",
    "        g = m * n\n",
    "        d = [0] * (4 * g + 1)\n",
    "        mod = 12345\n",
    "        def build(s, t, p):\n",
    "            # 对 [s,t] 区间建立线段树,当前根的编号为 p\n",
    "            if s == t:\n",
    "                tt = s - 1\n",
    "                d[p] = a[tt // n][tt % n]\n",
    "                return\n",
    "            mid = s + ((t - s) >> 1)\n",
    "            # 移位运算符的优先级小于加减法，所以加上括号\n",
    "            # 如果写成 (s + t) >> 1 可能会超出 int 范围\n",
    "            build(s, mid, p * 2); build(mid + 1, t, p * 2 + 1)\n",
    "            # 递归对左右区间建树\n",
    "            d[p] = d[p * 2] * d[(p * 2) + 1] % mod\n",
    "\n",
    "        def getmul(l, r, s, t, p):\n",
    "            if l > r: return 1\n",
    "            #print(1)\n",
    "            # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号\n",
    "            if l <= s and t <= r:\n",
    "                return d[p] # 当前区间为询问区间的子集时直接返回当前区间的和\n",
    "            mid = s + ((t - s) >> 1); mul = 1\n",
    "            if l <= mid:\n",
    "                mul = mul * getmul(l, r, s, mid, p * 2) % mod\n",
    "            # 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子\n",
    "            if r > mid:\n",
    "                mul = mul * getmul(l, r, mid + 1, t, p * 2 + 1) % mod\n",
    "            # 如果右儿子代表的区间 [m + 1, t] 与询问区间有交集, 则递归查询右儿子\n",
    "            return mul\n",
    "        build(1, g, 1)\n",
    "        #print(d)\n",
    "        res = [[1] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                kk = i * n + j + 1\n",
    "                res[i][j] = getmul(1, kk - 1, 1, g, 1) * getmul(kk + 1, g, 1, g, 1) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        suf = [[1] * n for _ in range(m)]\n",
    "        cur = 1\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                suf[i][j] = cur\n",
    "                cur = cur * grid[i][j] % mod\n",
    "        pres = 1\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = pres * suf[i][j] % mod\n",
    "                pres = pres * grid[i][j] % mod\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, g: List[List[int]]) -> List[List[int]]:\n",
    "        s = 1\n",
    "        mod = 12345\n",
    "        n, m = len(g), len(g[0])\n",
    "        suf = [[1] * (m) for _ in range(n)]\n",
    "        x = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                suf[i][j] = x\n",
    "                x *= g[i][j] \n",
    "                x %= mod\n",
    "                \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(m):\n",
    "                t.append(s * suf[i][j] % mod)\n",
    "                s *= g[i][j]\n",
    "                s %= mod\n",
    "            res.append(t)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        max_pro = 1\n",
    "        glen = len(grid)\n",
    "        if glen > 0:\n",
    "            gglen = len(grid[0])\n",
    "        pre = [[1 for i in range(gglen)] for j in range(glen)]\n",
    "\n",
    "        for i in range(glen):\n",
    "            for j in range(gglen):\n",
    "                pre[i][j] = max_pro\n",
    "                max_pro=grid[i][j]*max_pro%12345 \n",
    "        #print(pre)\n",
    "        pos = [[1 for i in range(gglen)] for j in range(glen)]\n",
    "        max_pro = 1\n",
    "        for i in range(glen-1,-1,-1):\n",
    "            for j in range(gglen-1,-1,-1):\n",
    "                pre[i][j] = max_pro * pre[i][j] % 12345 \n",
    "                max_pro=max_pro*grid[i][j]\n",
    "\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        right = [[1] * n for _ in  range(m)]\n",
    "        temp = 1\n",
    "        for i, j in product(reversed(range(m)), reversed(range(n))):\n",
    "            right[i][j] = temp \n",
    "            temp = (temp * grid[i][j]) % 12345 \n",
    "        left = 1\n",
    "        res = [[0] * n for _ in  range(m)]\n",
    "        for i, j in product(range(m), range(n)):\n",
    "            res[i][j] = (right[i][j] * left) % 12345\n",
    "            left = (left * grid[i][j]) % 12345\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        mod = 12345\n",
    "\n",
    "        ls = [[grid[r][c] for c in range(n)] for r in range(m)]\n",
    "        rs = [[grid[r][c] for c in range(n)] for r in range(m)]\n",
    "        us = [-1]*m\n",
    "        ds = [-1]*m\n",
    "        \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                ls[r][c]=ls[r][c-1]*grid[r][c]%mod if c else grid[r][c]\n",
    "            for c in range(n-1,-1,-1):\n",
    "                rs[r][c]=rs[r][c+1]*grid[r][c]%mod if c<n-1 else grid[r][c]        \n",
    "\n",
    "        for r in range(m):\n",
    "            us[r]=us[r-1]*ls[r][-1]%mod if r else ls[r][-1]\n",
    "        for r in range(m-1,-1,-1):\n",
    "            ds[r]=ds[r+1]*ls[r][-1]%mod if r<m-1 else ls[r][-1]\n",
    "                    \n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                u = us[r-1] if r else 1\n",
    "                d = ds[r+1] if r<m-1 else 1\n",
    "                l = ls[r][c-1] if c else 1\n",
    "                rr = rs[r][c+1] if c<n-1 else 1\n",
    "                grid[r][c]=u*d*l*rr%mod\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod=12345\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        t=n*m\n",
    "        ans=[[0]*m for _ in range(n)]\n",
    "        pre=[0]*t\n",
    "        suf=[0]*t\n",
    "        \n",
    "        @cache\n",
    "        def get(i):\n",
    "            return grid[i//m][i%m]\n",
    "        def set(i,v):\n",
    "            grid[i//m][i%m]=v\n",
    "        pre[0]=get(0)%mod\n",
    "        for i in range(1,t):\n",
    "            pre[i]=pre[i-1]*get(i)%mod\n",
    "        suf[-1]=get(t-1)%mod\n",
    "        for i in range(t-2,-1,-1):\n",
    "            suf[i]=suf[i+1]*get(i)%mod\n",
    "        set(0,suf[1])\n",
    "        set(t-1,pre[t-2])\n",
    "        for i in range(1,t-1):\n",
    "            set(i,pre[i-1]*suf[i+1]%mod)\n",
    "        return grid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 12345\n",
    "\n",
    "\n",
    "def gcd(a, b):\n",
    "    if a > b:\n",
    "        a, b = b, a\n",
    "\n",
    "    while a:\n",
    "        a, b = b % a, a\n",
    "    return b\n",
    "\n",
    "\n",
    "def get_prime(N):\n",
    "    prime_vals = []\n",
    "    flag = [True] * (N + 1)\n",
    "    for val in range(2, N + 1):\n",
    "        if flag[val]:\n",
    "            prime_vals.append(val)\n",
    "\n",
    "        for p_val in prime_vals:\n",
    "            if val * p_val > N:\n",
    "                break\n",
    "\n",
    "            flag[val * p_val] = False\n",
    "\n",
    "            if val % p_val == 0:\n",
    "                break\n",
    "\n",
    "    return prime_vals\n",
    "\n",
    "\n",
    "primes = get_prime(34000)  # 注意这里的100000需要大于等于 sqrt(最大的需要分解质因数的数值)\n",
    "\n",
    "\n",
    "# 分解质因数函数，返回元组数组[ (质因子1, 次幂1)， (质因子2, 次幂2)， (质因子3, 次幂3) ...... ]\n",
    "# 质因子的数值升序排列\n",
    "def devide_prime(val):\n",
    "    ans = {}\n",
    "\n",
    "\n",
    "    for i in primes:\n",
    "        if i * i > val:\n",
    "            break\n",
    "\n",
    "        if val % i == 0:\n",
    "            cnt = 0\n",
    "            while val % i == 0:\n",
    "                val //= i\n",
    "                cnt += 1\n",
    "\n",
    "            ans[i] = cnt\n",
    "\n",
    "        if val == 1:\n",
    "            break\n",
    "\n",
    "    # 特判最后可能剩下的大于sqrt(val)的最大的质因子\n",
    "    if val != 1:\n",
    "        ans[val] = 1\n",
    "\n",
    "    return ans\n",
    "\n",
    "def pow_mod(a, k, p):\n",
    "    ans = 1\n",
    "    pow_val = a % p  # a的2^0次方，数值就是a\n",
    "    while k != 0:\n",
    "        if k & 1 != 0:\n",
    "            ans = (ans * pow_val) % p\n",
    "        pow_val = (pow_val ** 2) % p\n",
    "        k >>= 1\n",
    "    return ans\n",
    "\n",
    "\n",
    "# 求a, b最大公约数，同时求出裴蜀定理中的一组系数x, y， 满足x*a + y*b = gcd(a, b)\n",
    "def exp_gcd(a, b):\n",
    "    flag = True\n",
    "    if a > b:\n",
    "        flag = False\n",
    "        a, b = b, a\n",
    "\n",
    "    if a == 0:\n",
    "        return (b, 0, 1) if flag else (b, 1, 0)\n",
    "\n",
    "    gcd_val, x, y = exp_gcd(b % a, a)\n",
    "    new_x = y - x * (b // a)\n",
    "    new_y = x\n",
    "    return (gcd_val, new_x, new_y) if flag else (gcd_val, new_y, new_x)\n",
    "\n",
    "\n",
    "# 求val对mod取模的逆元, 也就是求出的ans满足(val * ans) 和 1 对 mod 求模同余\n",
    "def get_mul_mod_rev_meta(val, mod):\n",
    "    gcd_val, x, _ = exp_gcd(val, mod)\n",
    "    return None if gcd_val != 1 else x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        c = Counter()\n",
    "        mm = {}\n",
    "\n",
    "        c1, c2, c3 = 0, 0, 0\n",
    "        for ll in grid:\n",
    "            for v in ll:\n",
    "                c[v] += 1\n",
    "\n",
    "                if v != 1:\n",
    "                    div = devide_prime(v)\n",
    "                    for p, cnt in div.items():\n",
    "                        if p == 3:\n",
    "                            c1 += 1\n",
    "                        if p == 5:\n",
    "                            c2 += 1\n",
    "                        if p == 823:\n",
    "                            c3 += 1\n",
    "\n",
    "                        if p not in mm:\n",
    "                            mm[p] = 0\n",
    "                        mm[p] += cnt\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if c1 >= 2 and c2 >= 2 and c3 >= 2:\n",
    "            return [[0] * n for i in range(m)]\n",
    "\n",
    "        Tot = 1\n",
    "        for val, cnt in c.items():\n",
    "            Tot *= pow_mod(val, cnt, MOD)\n",
    "            Tot %= MOD\n",
    "\n",
    "        kk = {}\n",
    "        for p, cnt in mm.items():\n",
    "            kk[p] = pow_mod(p, cnt, MOD)\n",
    "\n",
    "        p_arr = list(mm.keys())\n",
    "        N = len(p_arr)\n",
    "        p2idx = {}\n",
    "        for i in range(N):\n",
    "            p2idx[p_arr[i]] = i\n",
    "\n",
    "        vals = [0] * (4 * N + 100)\n",
    "        if N == 0:\n",
    "            return [[1]*n for i in range(m)]\n",
    "\n",
    "        def push_up(x):\n",
    "            vals[x] = vals[x << 1] * vals[(x<<1) + 1]\n",
    "            vals[x] %= MOD\n",
    "\n",
    "        def build(x, l, r):\n",
    "            if l == r:\n",
    "                p = p_arr[l]\n",
    "                vals[x] = kk[p]\n",
    "                return\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            build(x<<1, l, mid)\n",
    "            build((x<<1) | 1, mid+1, r)\n",
    "            push_up(x)\n",
    "\n",
    "        def query(x, l, r, ql, qr):\n",
    "            if l == ql and r == qr:\n",
    "                return vals[x]\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            if qr <= mid:\n",
    "                return query(x<<1, l, mid, ql, qr)\n",
    "            elif ql >= mid+1:\n",
    "                return query((x<<1)|1, mid+1, r, ql, qr)\n",
    "            else:\n",
    "                val1 = query(x<<1, l, mid, ql, mid)\n",
    "                val2 = query((x<<1)|1, mid+1, r, mid+1, qr)\n",
    "                return (val1 * val2) % MOD\n",
    "\n",
    "        build(1, 0, N-1)\n",
    "\n",
    "\n",
    "        cc = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = [[0] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] in cc:\n",
    "                    ret[i][j] = cc[grid[i][j]]\n",
    "                    continue\n",
    "\n",
    "                if grid[i][j] == 1:\n",
    "                    ret[i][j] = Tot\n",
    "                    cc[grid[i][j]] = Tot\n",
    "                    continue\n",
    "\n",
    "                if c1 >= 2 and c2 >= 2 and c3 >= 2:\n",
    "                    ret[i][j] = 0\n",
    "                    cc[grid[i][j]] = 0\n",
    "                    continue\n",
    "\n",
    "                if gcd(grid[i][j], MOD) != 1:\n",
    "                    if c1 == 1 and c2 == 1 and c3 == 1:\n",
    "                        f = False\n",
    "                        if grid[i][j] % 3 == 0:\n",
    "                            f = True\n",
    "                        if grid[i][j] % 5 == 0:\n",
    "                            f = True\n",
    "                        if grid[i][j] % 823 == 0:\n",
    "                            f = True\n",
    "\n",
    "                        if not f:\n",
    "                            ret[i][j] = 0\n",
    "                            cc[grid[i][j]] = 0\n",
    "                            continue\n",
    "\n",
    "                    div = devide_prime(grid[i][j])\n",
    "                    idx_arr = [p2idx[k] for k in div.keys()]\n",
    "                    idx_arr.sort()\n",
    "\n",
    "                    ans = 1\n",
    "                    prev_idx = -1\n",
    "\n",
    "                    for idx in idx_arr:\n",
    "                        a, b = prev_idx+1, idx - 1\n",
    "\n",
    "                        p = p_arr[idx]\n",
    "                        p_cnt = mm[p] - div[p]\n",
    "                        ans *= pow_mod(p, p_cnt, MOD)\n",
    "                        ans %= MOD\n",
    "\n",
    "                        if b >= a:\n",
    "                            ans *= query(1, 0, N-1, a, b)\n",
    "                            ans %= MOD\n",
    "\n",
    "                        prev_idx = idx\n",
    "\n",
    "                    lst_idx = idx_arr[-1]\n",
    "                    if lst_idx + 1 <= N-1:\n",
    "                        ans *= query(1, 0, N-1, lst_idx+1, N-1)\n",
    "                        ans %= MOD\n",
    "\n",
    "\n",
    "                    ret[i][j] = ans\n",
    "                    cc[grid[i][j]] = ans\n",
    "\n",
    "                else:\n",
    "                    rev = get_mul_mod_rev_meta(grid[i][j], MOD)\n",
    "                    ret[i][j] = (Tot * rev) % MOD\n",
    "                    cc[grid[i][j]] = ret[i][j]\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        suf = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 and j==0:\n",
    "                    pre[i][j] = 1\n",
    "                elif j == 0:\n",
    "                    pre[i][j] = pre[i-1][n-1]* grid[i-1][n-1]%12345\n",
    "                else:\n",
    "                    pre[i][j] = pre[i][j-1]* grid[i][j-1]%12345\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if i==m-1 and j==n-1:\n",
    "                    suf[i][j] = 1\n",
    "                elif j==n-1:\n",
    "                    suf[i][j] = suf[i+1][0] * grid[i+1][0]%12345\n",
    "                else:\n",
    "                    suf[i][j] = suf[i][j+1] *grid[i][j+1]%12345\n",
    "        result = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                result[i][j] = pre[i][j]*suf[i][j]%12345\n",
    "                \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        sumnum = 1\n",
    "        modnum = 12345\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        after = [[1]*n for _ in range(m)]\n",
    "        ans = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                print(i,j)\n",
    "                pre[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        sumnum = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                after[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre[i][j] * after[i][j]) % modnum\n",
    "        # print(grid, pre, after, ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "    利用前后缀分解分别计算前面与后面的数的乘积\n",
    "    重点: 从左向右 从上向下拉直为一个一维向量\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        mod = 12345\n",
    "        num = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[i][j] = num\n",
    "                num = (num * grid[i][j]) % mod\n",
    "\n",
    "        suf = [[1]*n for _ in range(m)]\n",
    "        mod = 12345\n",
    "        num = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                suf[i][j] = num\n",
    "                num = (num * grid[i][j]) % mod\n",
    "        \n",
    "        return [[pre[i][j]*suf[i][j]%mod for j in range(n)] for i in range(m)]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "M = 12345\n",
    "\n",
    "mulmod = np.frompyfunc(lambda a, b: a * b % M ,2 ,1)\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        grid = np.concatenate(([1], np.array(grid).flatten().astype(int), [1]))\n",
    "        prefix = mulmod.accumulate(grid[:-2])\n",
    "        suffix = np.flip(mulmod.accumulate(np.flip(grid[2:])))\n",
    "        return (prefix * suffix % M).reshape((n, -1)).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        sumnum = 1\n",
    "        modnum = 12345\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        pre = [[1]*n for _ in range(m)]\n",
    "        after = [[1]*n for _ in range(m)]\n",
    "        ans = [[1]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                print(i,j)\n",
    "                pre[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        sumnum = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                after[i][j] = sumnum\n",
    "                sumnum = (sumnum * grid[i][j]) % modnum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre[i][j] * after[i][j]) % modnum\n",
    "        print(grid, pre, after, ans)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        pre = [[1 for j in range(m)] for i in range(n)]\n",
    "        post = [[1 for j in range(m)] for i in range(n)]\n",
    "        prod = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i][j] = prod\n",
    "                prod = prod * grid[i][j] % 12345\n",
    "        prod = 1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(m-1, -1, -1):\n",
    "                post[i][j] = prod\n",
    "                prod = prod * grid[i][j] % 12345\n",
    "        \n",
    "        return [[pre[i][j] * post[i][j] % 12345 for j in range(m)] for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD=12345\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        row=[]\n",
    "        suf_col=[[1] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            mul=1\n",
    "            for j in range(n):\n",
    "                mul=mul*grid[i][j]%MOD\n",
    "                suf_col[i].append(suf_col[i][-1]*grid[i][-1-j]%MOD)\n",
    "            row.append(mul)\n",
    "        pre_m=[1]\n",
    "        for i in range(m):\n",
    "            pre_m.append(pre_m[-1]*row[i]%MOD)\n",
    "        suf_m=[1]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            suf_m.append(suf_m[-1]*row[i]%MOD)\n",
    "        ans=[[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            pre_col=1\n",
    "            for j in range(n):\n",
    "                ans[i][j]=pre_m[i]*suf_m[m-i-1]*pre_col*suf_col[i][n-j-1]%MOD\n",
    "                pre_col=pre_col*grid[i][j]%MOD\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from itertools import accumulate\n",
    "M = 12345\n",
    "\n",
    "mulmod = lambda a, b: a * b % M\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        grid = np.array(grid).flatten().tolist()\n",
    "        prefix = np.array(list(accumulate(grid[:-1], initial=1, func=mulmod)))\n",
    "        suffix = np.array(list(accumulate(grid[n*m-1:0:-1], initial=1,func=mulmod)))\n",
    "        return np.reshape(prefix * np.flip(suffix) % M, (n, m)).tolist()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        pre = [[1] * (m + 1) for _ in range(n)]\n",
    "        suf = [[1] * (m + 1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pre[i][j] = pre[i][j - 1] * grid[i][j] % 12345\n",
    "            for j in range(m)[::-1]:\n",
    "                suf[i][j] = suf[i][j + 1] * grid[i][j] % 12345\n",
    "        PRE = [1] * (n + 1)\n",
    "        SUF = [1] * (n + 1)\n",
    "        for i in range(n):\n",
    "            PRE[i] = PRE[i - 1] * pre[i][m - 1] % 12345\n",
    "        for i in range(n)[::-1]:\n",
    "            SUF[i] = SUF[i + 1] * pre[i][m - 1] % 12345\n",
    "        ans = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            x = PRE[i - 1] * SUF[i + 1]\n",
    "            for j in range(m):\n",
    "                y = pre[i][j - 1] * suf[i][j + 1]\n",
    "                ans[i][j] = x * y % 12345\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        mod = 12345\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        p = [[1] * m for _ in range(n)]\n",
    "        gpre = [1] * n\n",
    "        gsuf = [1] * n\n",
    "        rpre = [[1] * m for _ in range(n)]\n",
    "        rsuf = [[1] * m for _ in range(n)]\n",
    "        \n",
    "        for i in range(n):\n",
    "            now = 1\n",
    "            for j in range(m):\n",
    "                now = now * grid[i][j] % mod\n",
    "                rpre[i][j] = now\n",
    "            \n",
    "            now = 1\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                now = now * grid[i][j] % mod\n",
    "                rsuf[i][j] = now\n",
    "        \n",
    "        now = 1\n",
    "        for i in range(n):\n",
    "            now = now * rpre[i][-1] % mod\n",
    "            gpre[i] = now\n",
    "            \n",
    "        now = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            now = now * rpre[i][-1] % mod\n",
    "            gsuf[i] = now\n",
    "            \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                p[i][j] = 1\n",
    "                if i > 0:\n",
    "                    p[i][j] = p[i][j] * gpre[i - 1] % mod\n",
    "                if i + 1 < n:\n",
    "                    p[i][j] = p[i][j] * gsuf[i + 1] % mod\n",
    "                if j > 0:\n",
    "                    p[i][j] = p[i][j] * rpre[i][j - 1] % mod\n",
    "                if j + 1 < m:\n",
    "                    p[i][j] = p[i][j] * rsuf[i][j + 1] % mod\n",
    "            \n",
    "        return p\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        def func(grid):\n",
    "            import numpy as np\n",
    "            grid = np.array(grid)\n",
    "            h,w = grid.shape\n",
    "\n",
    "            grid_flatten = grid.reshape(h*w)\n",
    "            p = np.zeros_like(grid_flatten)\n",
    "\n",
    "            grid_flatten = grid_flatten%12345\n",
    "\n",
    "            pre_list = []\n",
    "            suf_list = []\n",
    "            # 正向\n",
    "            total = 1\n",
    "            for i in range(h*w):\n",
    "                if grid_flatten[i]==0:\n",
    "                    total = 0\n",
    "                total = total*grid_flatten[i] % 12345\n",
    "                pre_list.append(total)\n",
    "\n",
    "            total = 1\n",
    "            for i in range(h*w-1,-1,-1):\n",
    "                if grid_flatten[i]==0:\n",
    "                    total =0\n",
    "                total = total*grid_flatten[i] % 12345\n",
    "                suf_list.insert(0,total)\n",
    "\n",
    "            p[0] = suf_list[1]\n",
    "            p[-1] = pre_list[-2]\n",
    "            for i in range(1,h*w-1):\n",
    "                p[i] = pre_list[i-1]*suf_list[i+1] % 12345\n",
    "\n",
    "            return p.reshape(h,w).tolist()\n",
    "        \n",
    "        return func(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        MOD = 12345\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre_row = [1] * (m+2)\n",
    "        suff_row = [1] * (m+2)\n",
    "        total_mod = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "            pre_row[i+1] = total_mod\n",
    "            \n",
    "        total_mod = 1\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "            suff_row[i+1] = total_mod\n",
    "            \n",
    "        pre_col = [[1] * (n+2) for _ in range(m)]\n",
    "        suff_col = [[1] * (n+2) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            total_mod = 1\n",
    "            for j in range(n):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "                pre_col[i][j+1] = total_mod\n",
    "        for i in range(m):\n",
    "            total_mod = 1\n",
    "            for j in range(n-1, -1, -1):\n",
    "                total_mod = (total_mod*grid[i][j]) % MOD\n",
    "                suff_col[i][j+1] = total_mod       \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = (pre_row[i] * suff_row[i+2] * pre_col[i][j] * suff_col[i][j+2])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "def pow_mod(a, b, MOD):\n",
    "    res = 1\n",
    "    while b:\n",
    "        if b & 0x1:\n",
    "            res = (res * a) % MOD\n",
    "        a = (a * a) % MOD\n",
    "        b = b >> 1\n",
    "    return res\n",
    "\n",
    "\n",
    "def extended_gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a, 1, 0\n",
    "    else:\n",
    "        d, x1, y1 = extended_gcd(b, a % b)\n",
    "        x = y1\n",
    "        y = x1 - (a // b) * y1\n",
    "        return d, x, y\n",
    "\n",
    "\n",
    "# 相比费马小定理，这里不要求MOD是质数，只需要确保b和MOD是互质就行\n",
    "# b * x + MOD * y =  1(% MOD)\n",
    "def mod_inverse(b, MOD):\n",
    "    d, x, y = extended_gcd(b, MOD)\n",
    "    assert (d == 1)\n",
    "    return x % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        # 12345 = 3,5,823\n",
    "        MOD = 12345\n",
    "        A, B, C, D = 0, 0, 0, 1\n",
    "        encode = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                a, b, c = 0, 0, 0\n",
    "                x = grid[i][j]\n",
    "                while x % 3 == 0:\n",
    "                    a += 1\n",
    "                    x = x // 3\n",
    "                while x % 5 == 0:\n",
    "                    b += 1\n",
    "                    x = x // 5\n",
    "                while x % 823 == 0:\n",
    "                    c += 1\n",
    "                    x = x // 823\n",
    "                encode[(i, j)] = (a, b, c, x)\n",
    "                A, B, C = A + a, B + b, C + c\n",
    "                D = (D * x) % MOD\n",
    "\n",
    "        # print(A, B, C, D)\n",
    "        ans = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                a, b, c, d = encode[(i, j)]\n",
    "                # (D/d) % MOD\n",
    "                # D % MOD * (d^(-1) % MOD)\n",
    "                v = D * mod_inverse(d, MOD)\n",
    "                v = (v * pow_mod(3, (A - a), MOD)) % MOD\n",
    "                v = (v * pow_mod(5, (B - b), MOD)) % MOD\n",
    "                v = (v * pow_mod(823, (C - c), MOD)) % MOD\n",
    "                ans[i][j] = v\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 12345\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        c = Counter()\n",
    "        mm = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        Tot = 1\n",
    "        pos = {}\n",
    "        arr = []\n",
    "        for i, ll in enumerate(grid):\n",
    "            for j, v in enumerate(ll):\n",
    "                Tot *= v\n",
    "                Tot %= MOD\n",
    "                pos[v] = i*n + j\n",
    "                arr.append(v)\n",
    "\n",
    "        N = m*n\n",
    "        vals = [0] * (4 * N + 100)\n",
    "\n",
    "        def push_up(x):\n",
    "            vals[x] = vals[x << 1] * vals[(x<<1) + 1]\n",
    "            vals[x] %= MOD\n",
    "\n",
    "        def build(x, l, r):\n",
    "            if l == r:\n",
    "                vals[x] = arr[l] % MOD\n",
    "                return\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            build(x<<1, l, mid)\n",
    "            build((x<<1) | 1, mid+1, r)\n",
    "            push_up(x)\n",
    "\n",
    "        def query(x, l, r, ql, qr):\n",
    "            if l == ql and r == qr:\n",
    "                return vals[x]\n",
    "\n",
    "            mid = (l + r) >> 1\n",
    "            if qr <= mid:\n",
    "                return query(x<<1, l, mid, ql, qr)\n",
    "            elif ql >= mid+1:\n",
    "                return query((x<<1)|1, mid+1, r, ql, qr)\n",
    "            else:\n",
    "                val1 = query(x<<1, l, mid, ql, mid)\n",
    "                val2 = query((x<<1)|1, mid+1, r, mid+1, qr)\n",
    "                return (val1 * val2) % MOD\n",
    "\n",
    "        build(1, 0, N-1)\n",
    "\n",
    "\n",
    "        cc = {}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = [[0] * n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "\n",
    "                # if grid[i][j] in cc:\n",
    "                #     ret[i][j] = cc[grid[i][j]]\n",
    "                #     continue\n",
    "\n",
    "                idx = pos[grid[i][j]]\n",
    "                ans = 1\n",
    "                if idx-1 >= 0:\n",
    "                    ans *= query(1, 0, N-1, 0, idx-1)\n",
    "                    ans %= MOD\n",
    "\n",
    "                if idx+1 <= N-1:\n",
    "                    ans *= query(1, 0, N-1, idx+1, N-1)\n",
    "                    ans %= MOD\n",
    "\n",
    "                ret[i][j] = ans\n",
    "                cc[grid[i][j]] = ans\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_prime_factors(n):\n",
    "    ans = []\n",
    "    i = 2\n",
    "    while i <= sqrt(n):\n",
    "        while n % i == 0:\n",
    "            ans.append(i)\n",
    "            n //= i\n",
    "        i += 1\n",
    "    if n > 1:\n",
    "        ans.append(n)\n",
    "    return ans\n",
    "\n",
    "def exgcd(a, b):\n",
    "    if b == 0:\n",
    "        x = 1\n",
    "        y = 0\n",
    "        return x, y\n",
    "    x1, y1 = exgcd(b, a % b)\n",
    "    x = y1\n",
    "    y = x1 - (a // b) * y1\n",
    "    return x, y\n",
    "\n",
    "# If gcd(a, mod) = 1, return x such that a * x % mod = 1.\n",
    "def inv(a, mod):\n",
    "    x, y = exgcd(a, mod)\n",
    "    return ((x % mod) + mod) % mod\n",
    "\n",
    "# Chinese Remainder Theory\n",
    "# k = len(mod) = len(r)\n",
    "# x % mod[i] = r[i], 0 <= i < k\n",
    "# Return x % (mod[0] * mod[1] * ... * mod[k-1])\n",
    "# CRT([3,5,7],[2,3,2]) = 23\n",
    "def CRT(mod, r):\n",
    "    k = len(r)\n",
    "    n = 1\n",
    "    ans = 0\n",
    "    for i in range(k):\n",
    "        n = n * mod[i]\n",
    "    for i in range(k):\n",
    "        m = n // mod[i]\n",
    "        b = inv(m, mod[i])\n",
    "        ans = (ans + r[i] * m * b % n) % n\n",
    "    return (ans % n + n) % n\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def calc(mod):\n",
    "            ans = [[0 for j in range(n)] for i in range(m)]\n",
    "            cnt = sum(int(grid[i][j] % mod == 0) for j in range(n) for i in range(m))\n",
    "            if cnt >= 2:\n",
    "                return ans\n",
    "            prod = 1\n",
    "            target = -1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] % mod == 0: \n",
    "                        target = (i, j)\n",
    "                        continue\n",
    "                    prod *= grid[i][j]\n",
    "                    prod %= mod\n",
    "            if cnt == 1:\n",
    "                i, j = target    \n",
    "                ans[i][j] = prod\n",
    "                return ans\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    ans[i][j] = prod * inv(grid[i][j], mod) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 12345 \n",
    "        primes = get_prime_factors(mod)\n",
    "\n",
    "        r = [[[] for j in range(n)] for i in range(m)]\n",
    "        for p in primes:\n",
    "            ret = calc(p)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    r[i][j].append(ret[i][j])\n",
    "\n",
    "        return [[CRT(primes, r[i][j]) for j in range(n)] for i in range(m)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        prime1 = 3\n",
    "        prime2 = 5\n",
    "        prime3 = 823\n",
    "        pow1 = prime1 - 2\n",
    "        pow2 = prime2 - 2\n",
    "        pow3 = prime3 - 2\n",
    "        divisor = 12345\n",
    "        multi1 = prime2 * prime3 * pow(prime2 * prime3, pow1, prime1)\n",
    "        multi2 = prime1 * prime3 * pow(prime1 * prime3, pow2, prime2)\n",
    "        multi3 = prime2 * prime1 * pow(prime2 * prime1, pow3, prime3)\n",
    "        print(multi1)\n",
    "        print(multi2)\n",
    "        print(multi3)\n",
    "        mod1 = 1\n",
    "        mod2 = 1\n",
    "        mod3 = 1\n",
    "        aa1 = aa2 = aa3 = None\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, num in enumerate(line):\n",
    "                if aa1 is None and num % prime1 == 0:\n",
    "                    aa1 = (i, j)\n",
    "                mod1 = mod1 * num % prime1\n",
    "                if aa2 is None and num % prime2 == 0:\n",
    "                    aa2 = (i, j)\n",
    "                mod2 = mod2 * num % prime2\n",
    "                if aa3 is None and num % prime3 == 0:\n",
    "                    aa3 = (i, j)\n",
    "                mod3 = mod3 * num % prime3\n",
    "        ans1 = []\n",
    "        ans2 = []\n",
    "        ans3 = []\n",
    "        for line in grid:\n",
    "            tmp1 = []\n",
    "            tmp2 = []\n",
    "            tmp3 = []\n",
    "            for num in line:\n",
    "                tmp1.append(mod1 * pow(num, pow1, prime1) % prime1)\n",
    "                tmp2.append(mod2 * pow(num, pow2, prime2) % prime2)\n",
    "                tmp3.append(mod3 * pow(num, pow3, prime3) % prime3)\n",
    "            ans1.append(tmp1)\n",
    "            ans2.append(tmp2)\n",
    "            ans3.append(tmp3)\n",
    "        if aa1:\n",
    "            x, y = aa1\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime1\n",
    "            ans1[x][y] = mod\n",
    "        if aa2:\n",
    "            x, y = aa2\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime2\n",
    "            ans2[x][y] = mod\n",
    "        if aa3:\n",
    "            x, y = aa3\n",
    "            mod = 1\n",
    "            for i, line in enumerate(grid):\n",
    "                for j, num in enumerate(line):\n",
    "                    if i == x and j == y:\n",
    "                        continue\n",
    "                    mod = mod * num % prime3\n",
    "            ans3[x][y] = mod\n",
    "        ans = []\n",
    "        for line1, line2, line3 in zip(ans1, ans2, ans3):\n",
    "            tmp = []\n",
    "            for num1, num2, num3 in zip(line1, line2, line3):\n",
    "                tmp.append((num1 * multi1 + num2 * multi2 + num3 * multi3) % divisor)\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def recur(grid):\n",
    "            n=len(grid)\n",
    "            _sum=sum([sum(row) for row in grid])\n",
    "            if _sum==0:\n",
    "                return Node(0,True)\n",
    "            if _sum==n*n:\n",
    "                return Node(1,True)\n",
    "            res=Node(0,False)\n",
    "            res.topLeft=recur([[grid[y][x] for x in range(n//2)] for y in range(n//2)])\n",
    "            res.topRight=recur([[grid[y][x] for x in range(n//2,n)] for y in range(n//2)])\n",
    "            res.bottomLeft=recur([[grid[y][x] for x in range(n//2)] for y in range(n//2,n)])\n",
    "            res.bottomRight=recur([[grid[y][x] for x in range(n//2,n)] for y in range(n//2,n)])\n",
    "            return res\n",
    "\n",
    "\n",
    "        return recur(grid)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def recur(grid):\n",
    "            n=len(grid)\n",
    "            _sum=sum([sum(row) for row in grid])\n",
    "            if _sum==0:\n",
    "                return Node(0,True)\n",
    "            if _sum==n*n:\n",
    "                return Node(1,True)\n",
    "            res=Node(0,False)\n",
    "            res.topLeft=recur([[grid[y][x] for x in range(n//2)] for y in range(n//2)])\n",
    "            res.topRight=recur([[grid[y][x] for x in range(n//2,n)] for y in range(n//2)])\n",
    "            res.bottomLeft=recur([[grid[y][x] for x in range(n//2)] for y in range(n//2,n)])\n",
    "            res.bottomRight=recur([[grid[y][x] for x in range(n//2,n)] for y in range(n//2,n)])\n",
    "            return res\n",
    "\n",
    "\n",
    "        return recur(grid)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def dfs(r0, r1, c0, c1):\n",
    "            for i in range(r0, r1):\n",
    "                for j in range(c0, c1):\n",
    "                    if grid[i][j] != grid[r0][c0]:\n",
    "                        return Node(\n",
    "                        grid[i][j], False, dfs(r0, (r0+r1)//2, c0, (c0+c1)//2),\n",
    "                        dfs(r0, (r0+r1)//2, (c0+c1)//2, c1), dfs((r0+r1)//2, r1, c0, (c0+c1)//2),\n",
    "                        dfs((r0+r1)//2, r1, (c0+c1)//2, c1)\n",
    "                        )\n",
    "            return Node(grid[r0][c0], True)\n",
    "        return dfs(0, len(grid), 0, len(grid))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        n = len(grid)\n",
    "        size = 1\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, n):\n",
    "                topLeft = grid[i][j]\n",
    "                topRight = grid[i][j+size//2]\n",
    "                bottomLeft = grid[i+size//2][j]\n",
    "                bottomRight = grid[i+size//2][j+size//2]\n",
    "                grid[i][j] = Node(topLeft,True,None,None,None,None)\n",
    "        size <<= 1\n",
    "        while size <= n:\n",
    "            for i in range(0, n, size):\n",
    "                for j in range(0, n, size):\n",
    "                    topLeft = grid[i][j]\n",
    "                    topRight = grid[i][j+size//2]\n",
    "                    bottomLeft = grid[i+size//2][j]\n",
    "                    bottomRight = grid[i+size//2][j+size//2]\n",
    "                    if topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and sum((topLeft.val,topRight.val,bottomLeft.val,bottomRight.val)) == topLeft.val * 4:\n",
    "                        grid[i][j] = Node(topLeft.val,True,None,None,None,None)\n",
    "                    else:\n",
    "                        grid[i][j] = Node(topLeft.val,False,topLeft,topRight,bottomLeft,bottomRight)\n",
    "            size <<= 1\n",
    "        return grid[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        n = len(grid)\n",
    "        pre = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + grid[i - 1][j - 1]\n",
    "\n",
    "        def getSum(r0: int, c0: int, r1: int, c1: int) -> int:\n",
    "            return pre[r1][c1] - pre[r1][c0] - pre[r0][c1] + pre[r0][c0]\n",
    "\n",
    "        def dfs(r0: int, c0: int, r1: int, c1: int) -> 'Node':\n",
    "            total = getSum(r0, c0, r1, c1)\n",
    "            if total == 0:\n",
    "                return Node(False, True)\n",
    "            if total == (r1 - r0) * (c1 - c0):\n",
    "                return Node(True, True)\n",
    "            return Node(\n",
    "                True,\n",
    "                False,\n",
    "                dfs(r0, c0, (r0 + r1) // 2, (c0 + c1) // 2),\n",
    "                dfs(r0, (c0 + c1) // 2, (r0 + r1) // 2, c1),\n",
    "                dfs((r0 + r1) // 2, c0, r1, (c0 + c1) // 2),\n",
    "                dfs((r0 + r1) // 2, (c0 + c1) // 2, r1, c1),\n",
    "            )\n",
    "\n",
    "        return dfs(0, 0, n, n)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        n=len(grid)\n",
    "        presum= [[0]*(n+1) for i in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                presum[i+1][j+1] += presum[i+1][j]+ presum[i][j+1] - presum[i][j]+grid[i][j]\n",
    "        def dfs(x0,y0,x1,y1):\n",
    "            diff = presum[x1][y1] - presum[x1][y0] - presum[x0][y1] + presum[x0][y0]\n",
    "            if not diff: return Node(False, True, None, None, None)\n",
    "            elif diff == (x1-x0)*(y1-y0): \n",
    "                return Node(True, True, None, None, None)\n",
    "            else:\n",
    "                hx=(x0 + x1) // 2\n",
    "                hy=(y0 + y1) // 2\n",
    "                return Node(True,False,dfs(x0,y0,hx,hy),\n",
    "                                       dfs(x0,hy,hx,y1),\n",
    "                                       dfs(hx,y0,x1,hy),\n",
    "                                       dfs(hx,hy,x1,y1))\n",
    "        return dfs(0,0,n,n)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 1: Recursive DFS\n",
    "    time:   T(n)=4T(n/2)+O(n^2), T(1)=O(1),\n",
    "        from master theorem, we get T(n) = O(logn * n^2)\n",
    "    space: O(logn) for the recursive stack\n",
    "    \"\"\"\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def dfs(n, row, col):\n",
    "            all_same = True\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[row][col] != grid[row+i][col+j]:\n",
    "                        all_same = False\n",
    "                        break\n",
    "            if all_same:\n",
    "                return Node(grid[row][col], True)\n",
    "\n",
    "            n = n // 2\n",
    "            top_left = dfs(n, row, col)\n",
    "            top_right = dfs(n, row, col+n)\n",
    "            bot_left = dfs(n, row+n, col)\n",
    "            bot_right = dfs(n, row+n, col+n)\n",
    "            return Node(0, False, top_left, top_right, bot_left, bot_right)\n",
    "        return dfs(len(grid), 0, 0)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    Approach 2: Recursive DFS + Prefix Sum\n",
    "    time:  T(n)=4T(n/2)+O(1), T(1)=O(1),\n",
    "        from master theorem, we get T(n) = O(n^2)\n",
    "    space: O(logn) for the recursive stack, O(n^2) for the prefix sum matrix <pre_sum>\n",
    "    \"\"\"\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        n = len(grid)\n",
    "        pre_sum = [[0] * (n+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, n+1):\n",
    "                pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + grid[i-1][j-1]\n",
    "\n",
    "        def get_sum(n, row, col) -> int:\n",
    "            return pre_sum[row+n][col+n] - pre_sum[row+n][col] - pre_sum[row][col+n] + pre_sum[row][col]\n",
    "\n",
    "        def dfs(n, row, col):\n",
    "            sum = get_sum(n, row, col)\n",
    "            if sum == 0 or sum == n**2:  # all elements are same\n",
    "              return Node(grid[row][col], True)\n",
    "\n",
    "            n = n // 2\n",
    "\n",
    "            top_left = dfs(n, row, col)\n",
    "            top_right = dfs(n, row, col+n)\n",
    "            bot_left = dfs(n, row+n, col)\n",
    "            bot_right = dfs(n, row+n, col+n)\n",
    "            return Node(0, False, top_left, top_right, bot_left, bot_right)\n",
    "        return dfs(n, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node' :\n",
    "        n = len(grid)\n",
    "        mid = n // 2  # 注意 mid不是index\n",
    "\n",
    "        tlval = grid[0][0]\n",
    "        trval = grid[0][mid]\n",
    "        blval = grid[mid][0]\n",
    "        brval = grid[mid][mid]\n",
    "\n",
    "        tlflag = trflag = blflag = brflag = True\n",
    "\n",
    "        tlgrid = []\n",
    "        trgrid = []\n",
    "        blgrid = []\n",
    "        brgrid = []\n",
    "\n",
    "        for row_index in range(n):\n",
    "            tlrow = []\n",
    "            trrow = []\n",
    "            blrow = []\n",
    "            brrow = []\n",
    "            for col_index in range(n) :\n",
    "                if row_index < mid and col_index < mid :\n",
    "                    tlrow.append(grid[row_index][col_index])\n",
    "                    if grid[row_index][col_index] != tlval :\n",
    "                        tlflag = False\n",
    "                elif row_index < mid and col_index >= mid :\n",
    "                    trrow.append(grid[row_index][col_index])\n",
    "                    if grid[row_index][col_index] != tlval:\n",
    "                        trflag = False\n",
    "                elif row_index >= mid and col_index < mid :\n",
    "                    blrow.append(grid[row_index][col_index])\n",
    "                    if grid[row_index][col_index] != tlval:\n",
    "                        blflag = False\n",
    "                elif row_index >= mid and col_index >= mid :\n",
    "                    brrow.append(grid[row_index][col_index])\n",
    "                    if grid[row_index][col_index] != tlval:\n",
    "                        brflag = False\n",
    "            if tlrow :\n",
    "                tlgrid.append(tlrow)\n",
    "            if trrow :\n",
    "                trgrid.append(trrow)\n",
    "            if blrow:\n",
    "                blgrid.append(blrow)\n",
    "            if brrow :\n",
    "                brgrid.append(brrow)\n",
    "\n",
    "        tlnode = Node(tlval,True,None,None,None,None) if tlflag else self.construct(tlgrid)\n",
    "        trnode = Node(trval,True,None,None,None,None) if trflag else self.construct(trgrid)\n",
    "        blnode = Node(blval, True, None, None, None, None) if blflag else self.construct(blgrid)\n",
    "        brnode = Node(brval, True, None, None, None, None) if brflag else self.construct(brgrid)\n",
    "\n",
    "        curflag = (tlflag and trflag and brflag and blflag)\n",
    "        curval = grid[0][0] if curflag else -1\n",
    "\n",
    "        return Node(curval,curflag,tlnode,trnode,blnode,brnode)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def dfs(i, j, dn):\n",
    "            if dn == 1:\n",
    "                d[(i, j, dn)] = grid[i][j]\n",
    "            else:\n",
    "                dn2 = dn // 2\n",
    "                v0 = dfs(i, j, dn2)\n",
    "                v1 = dfs(i, j + dn2, dn2)\n",
    "                v2 = dfs(i + dn2, j, dn2)\n",
    "                v3 = dfs(i + dn2, j + dn2, dn2)\n",
    "                if v0 == v1 == v2 == v3 and v0 != -1:\n",
    "                    d[(i, j, dn)] = v0\n",
    "                else:\n",
    "                    d[(i, j, dn)] = -1\n",
    "            return d[(i, j, dn)]\n",
    "\n",
    "        n = len(grid)\n",
    "        d = {}\n",
    "        dfs(0, 0, n)\n",
    "        if d[(0, 0, n)] == -1:\n",
    "            root = Node(0, 0, None, None, None, None)\n",
    "        else:\n",
    "            root = Node(d[(0, 0, n)], 1, None, None, None, None)\n",
    "        ans = []\n",
    "        d2 = {root: (0, 0, n)}\n",
    "        pre = [root]\n",
    "        while pre:\n",
    "            cur = []\n",
    "            for p in pre:\n",
    "                ans.append(p)\n",
    "                if p.isLeaf == 0:\n",
    "                    i, j, n = d2[p]\n",
    "                    if d[(i, j, n // 2)] == -1:\n",
    "                        p.topLeft = Node(0, 0, None, None, None, None)\n",
    "                    else:\n",
    "                        p.topLeft = Node(d[(i, j, n // 2)], 1, None, None, None, None)\n",
    "                    cur.append(p.topLeft)\n",
    "                    d2[p.topLeft] = (i, j, n // 2)\n",
    "\n",
    "                    if d[(i, j + n // 2, n // 2)] == -1:\n",
    "                        p.topRight = Node(0, 0, None, None, None, None)\n",
    "                    else:\n",
    "                        p.topRight = Node(d[(i, j + n // 2, n // 2)], 1, None, None, None, None)\n",
    "                    cur.append(p.topRight)\n",
    "                    d2[p.topRight] = (i, j + n // 2, n // 2)\n",
    "\n",
    "                    if d[(i + n // 2, j, n // 2)] == -1:\n",
    "                        p.bottomLeft = Node(0, 0, None, None, None, None)\n",
    "                    else:\n",
    "                        p.bottomLeft = Node(d[(i + n // 2, j, n // 2)], 1, None, None, None, None)\n",
    "                    cur.append(p.bottomLeft)\n",
    "                    d2[p.bottomLeft] = (i + n // 2, j, n // 2)\n",
    "\n",
    "                    if d[(i + n // 2, j + n // 2, n // 2)] == -1:\n",
    "                        p.bottomRight = Node(0, 0, None, None, None, None)\n",
    "                    else:\n",
    "                        p.bottomRight = Node(d[(i + n // 2, j + n // 2, n // 2)], 1, None, None, None, None)\n",
    "                    cur.append(p.bottomRight)\n",
    "                    d2[p.bottomRight] = (i + n // 2, j + n // 2, n // 2)\n",
    "            pre = cur\n",
    "        return root\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        n = len(grid)\n",
    "        rec = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d = 1\n",
    "                while d<=n:\n",
    "                    ti,tj = (i//d)*d,(j//d)*d\n",
    "                    key = (ti,tj,ti+d-1,tj+d-1)\n",
    "                    if key not in rec:\n",
    "                        rec[key] = 0\n",
    "                    rec[key] |= 1<<(grid[i][j])\n",
    "                    d <<= 1\n",
    "        def _func(sx,sy,ex,ey):\n",
    "            key = (sx,sy,ex,ey)\n",
    "            if rec[key] < 3:\n",
    "                return Node(rec[key]-1,1,None,None,None,None)\n",
    "            mx,my = (sx+ex)//2,(sy+ey)//2\n",
    "            return Node(0,0,_func(sx,sy,mx,my),_func(sx,my+1,mx,ey),_func(mx+1,sy,ex,my),_func(mx+1,my+1,ex,ey))\n",
    "        return _func(0,0,n-1,n-1)\n",
    "'''\n",
    "[[1,1],[1,1]]\n",
    "[[0]]\n",
    "[[0,1],[1,0]]\n",
    "[[1,1,0,0],[1,1,0,0],[0,0,1,1],[0,0,1,1]]\n",
    "[[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,1,1,1,1],[1,1,1,1,1,1,1,1],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0],[1,1,1,1,0,0,0,0]]\n",
    "\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "from numpy import array\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def construct(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        root =  Node('*',True,None,None,None,None)\n",
    "        if len(grid) == 1:\n",
    "            root.isLeaf = True\n",
    "            root.val = True if grid[0][0] == 1 else False\n",
    "        if self.allsumvalue(grid):\n",
    "            root.isLeaf = True\n",
    "            root.val = True if grid[0][0] == 1 else False\n",
    "        else:\n",
    "            root.isLeaf = False\n",
    "            halflengh = len(grid) // 2\n",
    "            root.topLeft = self.construct(np.array(grid)[:halflengh,:halflengh].tolist())\n",
    "            root.topRight = self.construct(np.array(grid)[:halflengh,halflengh:].tolist())\n",
    "            root.bottomLeft = self.construct(np.array(grid)[halflengh:,:halflengh].tolist())\n",
    "            root.bottomRight = self.construct(np.array(grid)[halflengh:,halflengh:].tolist())\n",
    "        return root\n",
    "               \n",
    "\n",
    "    def allsumvalue(self,grid):\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        value = grid[0][0]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] != value:\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "from numpy import array\n",
    "class Solution:\n",
    "    def construct(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        root =  Node('*',True,None,None,None,None)\n",
    "        if len(grid) == 1:\n",
    "            root.isLeaf = True\n",
    "            root.val = True if grid[0][0] == 1 else False\n",
    "        if self.allsumvalue(grid):\n",
    "            root.isLeaf = True\n",
    "            root.val = True if grid[0][0] == 1 else False\n",
    "        else:\n",
    "            root.isLeaf = False\n",
    "            halflengh = len(grid) // 2\n",
    "            root.topLeft = self.construct(array(grid)[:halflengh,:halflengh].tolist())\n",
    "            root.topRight = self.construct(array(grid)[:halflengh,halflengh:].tolist())\n",
    "            root.bottomLeft = self.construct(array(grid)[halflengh:,:halflengh].tolist())\n",
    "            root.bottomRight = self.construct(array(grid)[halflengh:,halflengh:].tolist())\n",
    "        return root\n",
    "               \n",
    "\n",
    "    def allsumvalue(self,grid):\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        value = grid[0][0]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] != value:\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        @lru_cache(None)\n",
    "        def dfs(x0:int,y0:int,x1:int,y1:int)->'Node':\n",
    "            if x0==x1 and y0==y1:\n",
    "                return Node(grid[y1][x1],1,None,None,None,None)\n",
    "            n = (x1-x0 + 1)//2\n",
    "            tl = dfs(x0,y0,x0+n-1,y0+n-1)\n",
    "            tr = dfs(x0+n,y0,x1,y0+n-1)\n",
    "            bl = dfs(x0,y0+n,x0+n-1,y1)\n",
    "            br = dfs(x0+n,y0+n,x1,y1)\n",
    "            if tl.isLeaf == tr.isLeaf == bl.isLeaf == br.isLeaf == 1 and tl.val == tr.val == bl.val == br.val:\n",
    "                return Node(grid[y1][x1],1,None,None,None,None)\n",
    "            return Node(1,0,tl,tr,bl,br)\n",
    "        return dfs(0,0,len(grid)-1,len(grid)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        @lru_cache(None)\n",
    "        def dfs(x0:int,y0:int,x1:int,y1:int)->'Node':\n",
    "            if x0==x1 and y0==y1:\n",
    "                return Node(grid[y1][x1],1,None,None,None,None)\n",
    "            n = (x1-x0 + 1)//2\n",
    "            tl = dfs(x0,y0,x0+n-1,y0+n-1)\n",
    "            tr = dfs(x0+n,y0,x1,y0+n-1)\n",
    "            bl = dfs(x0,y0+n,x0+n-1,y1)\n",
    "            br = dfs(x0+n,y0+n,x1,y1)\n",
    "            if tl.isLeaf == tr.isLeaf == bl.isLeaf == br.isLeaf == 1 and tl.val == tr.val == bl.val == br.val:\n",
    "                return Node(grid[y1][x1],1,None,None,None,None)\n",
    "            return Node(1,0,tl,tr,bl,br)\n",
    "        return dfs(0,0,len(grid)-1,len(grid)-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        if not grid:\n",
    "            return None\n",
    "        return self.helper(grid, 0, 0, len(grid))\n",
    "\n",
    "    def helper(self, grid, y, x, l):\n",
    "        if l == 0:\n",
    "            return Node(grid[y][x], True, None, None, None, None)\n",
    "        l >>= 1\n",
    "        tl = self.helper(grid, y, x, l)\n",
    "        tr = self.helper(grid, y, x + l, l)\n",
    "        bl = self.helper(grid, y + l, x, l)\n",
    "        br = self.helper(grid, y + l, x + l, l)\n",
    "        if (tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf) and \\\n",
    "           (tl.val == tr.val == bl.val == br.val):\n",
    "            return Node(tl.val, True, None, None, None, None)\n",
    "        else:\n",
    "            return Node(None, False, tl, tr, bl, br)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "    \n",
    "def construct1(grid):\n",
    "    n = len(grid)\n",
    "    if n == 1:\n",
    "        return Node(grid[0][0]==1, True, None, None, None, None)\n",
    "    \n",
    "    # 等分之后，进行递归\n",
    "    top_left = construct1(grid[0:n//2, 0:n//2])\n",
    "    top_right = construct1(grid[0:n//2, n//2:n])\n",
    "    bottom_left = construct1(grid[n//2:n, 0:n//2])\n",
    "    bottom_right = construct1(grid[n//2:n, n//2:n])\n",
    "    \n",
    "    # 检查是否四个子树全都一样\n",
    "    tmp1 = False\n",
    "    tmp2 = False\n",
    "    if top_left.isLeaf and top_right.isLeaf and bottom_left.isLeaf and bottom_right.isLeaf:\n",
    "        tmp1 = (False or top_left.val or top_right.val or bottom_left.val or bottom_right.val) == False\n",
    "        tmp2 = (True and top_left.val and top_right.val and bottom_left.val and bottom_right.val) == True\n",
    "        \n",
    "    if tmp1 or tmp2:\n",
    "        # 四个子树相同\n",
    "        return Node(top_left.val, True, None, None, None, None)\n",
    "    \n",
    "    return Node(None, False, top_left, top_right, bottom_left, bottom_right)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        import numpy as np\n",
    "        grid = np.array(grid)\n",
    "        return construct1(grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        import numpy as np\n",
    "        grid = np.array(grid)\n",
    "       \n",
    "        def is_leaf(grid, row, col):\n",
    "            return all(grid[i][j] == grid[0][0] for i in range(row) for j in range(col))\n",
    "        \n",
    "        def dfs(grid):\n",
    "            row = len(grid)\n",
    "            col = len(grid[0])\n",
    "            if is_leaf(grid, row, col):\n",
    "                return Node(\n",
    "                    grid[0][0] == 1,\n",
    "                    True,\n",
    "                    None,None,None,None\n",
    "                )\n",
    "            root = Node(\n",
    "                    \"*\", False, None,None,None,None\n",
    "            )\n",
    "            root.topLeft = dfs(grid[:row//2,:col//2])\n",
    "            root.topRight = dfs(grid[:row//2, col//2:])\n",
    "            root.bottomLeft = dfs(grid[row//2:,:col//2])\n",
    "            root.bottomRight = dfs(grid[row//2:, col//2:])\n",
    "            return root\n",
    "            \n",
    "        return dfs(grid)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "\n",
    "def grid_is_all_same(grid):\n",
    "    height, width = grid.shape[:2]\n",
    "    grid_num = np.sum(grid)\n",
    "    if grid_num == height * width or grid_num == 0:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def split_grid(grid):\n",
    "    height, width = grid.shape[:2]\n",
    "    w_mid = width // 2\n",
    "    h_mid = height // 2\n",
    "    topLeftGrid = grid[:h_mid, :w_mid]\n",
    "    topRightGrid = grid[:h_mid, w_mid:]\n",
    "    bottomLeftGrid = grid[h_mid:, :w_mid]\n",
    "    bottomRightGrid = grid[h_mid:, w_mid:]\n",
    "    return topLeftGrid, topRightGrid, bottomLeftGrid, bottomRightGrid\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        grid = np.asarray(grid)\n",
    "        root = Node(True, False, None, None, None, None)\n",
    "        self.help_construct(grid, root)\n",
    "        return root\n",
    "    \n",
    "    def help_construct(self, grid, cur_node):\n",
    "        if grid_is_all_same(grid):\n",
    "            cur_node.val = grid[0, 0]\n",
    "            cur_node.isLeaf = True\n",
    "            cur_node.topLeft = None\n",
    "            cur_node.topRight = None\n",
    "            cur_node.bottomLeft = None\n",
    "            cur_node.bottomRight = None\n",
    "        else:\n",
    "            sub_grids = split_grid(grid)\n",
    "            cur_node.topLeft = Node(1, False, None, None, None, None)\n",
    "            cur_node.topRight = Node(1, False, None, None, None, None)\n",
    "            cur_node.bottomLeft = Node(1, False, None, None, None, None)\n",
    "            cur_node.bottomRight = Node(1, False, None, None, None, None)\n",
    "\n",
    "            topLeftGrid, topRightGrid, bottomLeftGrid, bottomRightGrid = sub_grids\n",
    "            self.help_construct(topLeftGrid, cur_node.topLeft)\n",
    "            self.help_construct(topRightGrid, cur_node.topRight)\n",
    "            self.help_construct(bottomLeftGrid, cur_node.bottomLeft)\n",
    "            self.help_construct(bottomRightGrid, cur_node.bottomRight )\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        import numpy as np\n",
    "        grid = np.array(grid)\n",
    "       \n",
    "        def is_leaf(grid, row, col):\n",
    "            return all(grid[i][j] == grid[0][0] for i in range(row) for j in range(col))\n",
    "        \n",
    "        def dfs(grid):\n",
    "            row = len(grid)\n",
    "            col = len(grid[0])\n",
    "            if is_leaf(grid, row, col):\n",
    "                return Node(\n",
    "                    grid[0][0] == 1,\n",
    "                    True,\n",
    "                    None,None,None,None\n",
    "                )\n",
    "            root = Node(\n",
    "                    \"*\", False, None,None,None,None\n",
    "            )\n",
    "            root.topLeft = dfs(grid[:row//2,:col//2])\n",
    "            root.topRight = dfs(grid[:row//2, col//2:])\n",
    "            root.bottomLeft = dfs(grid[row//2:,:col//2])\n",
    "            root.bottomRight = dfs(grid[row//2:, col//2:])\n",
    "            return root\n",
    "            \n",
    "        return dfs(grid)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def construct(self, grid) -> 'Node':\n",
    "        grid = np.array(grid)\n",
    "        x = Node(False,False,None,None,None,None)\n",
    "        if len(grid) == 1:\n",
    "            x.isLeaf = True\n",
    "            x.val = grid[0,0]\n",
    "            return x\n",
    "        mid = len(grid)//2\n",
    "        topleftnode = self.construct(grid[0:mid,0:mid])\n",
    "        topRightnode = self.construct(grid[0:mid,mid:])\n",
    "        bottomleftnode = self.construct(grid[mid:,0:mid])\n",
    "        bottomrightnode = self.construct(grid[mid:,mid:])\n",
    "        if topleftnode.isLeaf and topRightnode.isLeaf and bottomleftnode.isLeaf and bottomrightnode.isLeaf and \\\n",
    "                (topleftnode.val == topRightnode.val == bottomrightnode.val == bottomleftnode.val):\n",
    "            x.val = topRightnode.val\n",
    "            x.isLeaf = True\n",
    "\n",
    "        else:\n",
    "            x.topLeft = topleftnode\n",
    "            x.topRight = topRightnode\n",
    "            x.bottomLeft = bottomleftnode\n",
    "            x.bottomRight = bottomrightnode\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "import numpy\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        grid = numpy.array(grid)\n",
    "        def QuadTree(grid,i,j,n):\n",
    "            if numpy.all(grid[i:i+n,j:j+n]==1):\n",
    "                tree = Node(True,True,None,None,None,None)\n",
    "            elif numpy.all(grid[i:i+n,j:j+n]==0):\n",
    "                tree = Node(False,True,None,None,None,None)\n",
    "            else:\n",
    "                topl = QuadTree(grid,i,j,n//2)\n",
    "                topr = QuadTree(grid,i,j+n//2,n//2)\n",
    "                bottoml = QuadTree(grid,i+n//2,j,n//2)\n",
    "                bottomr = QuadTree(grid,i+n//2,j+n//2,n//2)\n",
    "                tree = Node(True,False,topl,topr,bottoml,bottomr)\n",
    "            return tree \n",
    "        \n",
    "        return QuadTree(grid,0,0,len(grid))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        node = Node()\n",
    "        istrue = grid[0][0]\n",
    "        grid = np.array(grid)\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j != istrue:\n",
    "                    length = int(len(grid[0]) / 2)\n",
    "                    node.topLeft = self.construct(grid[0:length, 0:length])\n",
    "                    node.topRight = self.construct(grid[0:length, length:])\n",
    "                    node.bottomLeft = self.construct(grid[length:, 0:length])\n",
    "                    node.bottomRight = self.construct(grid[length:, length:])\n",
    "                    node.isLeaf = False\n",
    "                    node.val = True\n",
    "                    return node\n",
    "        node.val = istrue\n",
    "        node.isLeaf = True\n",
    "        return node        \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        if len(grid) == 0:\n",
    "            return Node(0, True)\n",
    "        \n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        \n",
    "        ave_sum = sum(map(sum,grid)) / (rows * cols)\n",
    "        \n",
    "        grid = np.array(grid)\n",
    "        \n",
    "        if ave_sum == 1:\n",
    "            root = Node(1, True)\n",
    "            return root\n",
    "        elif ave_sum == 0:\n",
    "            root = Node(0, True)\n",
    "            return root\n",
    "        else:\n",
    "            root = Node(1, False)   #本代码采用1\n",
    "        \n",
    "        \n",
    "        topLeft = grid[0:rows//2,0:cols//2]\n",
    "        topRight = grid[0:rows//2,cols//2:cols]\n",
    "        botLeft = grid[rows//2:rows,0:cols//2]\n",
    "        botRight = grid[rows//2:rows,cols//2:cols]\n",
    "\n",
    "        \n",
    "        root.topLeft = self.construct(topLeft)\n",
    "        root.topRight = self.construct(topRight)\n",
    "        root.bottomLeft = self.construct(botLeft)\n",
    "        root.bottomRight = self.construct(botRight)\n",
    "        \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        self.grid = grid\n",
    "        return self.dfs(0, len(grid), 0, len(grid))\n",
    "\n",
    "    def dfs(self, u, d, l, r):  #分别是上下左右四个位置\n",
    "        n = d - u \n",
    "        if self.isleaf(u, d, l, r):\n",
    "            return Node(self.grid[u][l], 1, None, None, None, None)\n",
    "        else:\n",
    "            node = Node(self.grid[u][l], 0, None, None, None, None)\n",
    "            node.topLeft     = self.dfs(u, u + n//2, l, l + n//2)\n",
    "            node.topRight    = self.dfs(u, u + n//2, l + n//2, l + n)\n",
    "            node.bottomLeft  = self.dfs(u + n//2, u + n, l, l + n//2)\n",
    "            node.bottomRight = self.dfs(u + n//2, u + n, l + n//2, l + n)\n",
    "            return node\n",
    "\n",
    "    def isleaf(self, u, d, l, r):\n",
    "        for i in range(u, d):\n",
    "            for j in range(l, r):\n",
    "                if self.grid[i][j] != self.grid[u][l]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import array\n",
    "class Solution:\n",
    "    def construct(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        root = Node('*', True, None, None, None, None);\n",
    "        if len(grid) == 1:\n",
    "            root.isLeaf = True;\n",
    "            root.val = True if grid[0][0] == 1 else False;\n",
    "        if self.allValueSame(grid):       # 所有值相等\n",
    "            root.isLeaf = True;\n",
    "            root.val = True if grid[0][0] == 1 else False;\n",
    "        else:                             # 并非所有值相等\n",
    "            halfLength = len(grid) // 2;  # 使用 // 表示整除\n",
    "            root.isLeaf = False;          # 如果网格中有值不相等，这个节点就不是叶子节点\n",
    "            # 使用array来完成二维数组的切片\n",
    "            root.topLeft = self.construct(array(grid)[:halfLength, :halfLength].tolist());\n",
    "            root.topRight = self.construct(array(grid)[:halfLength, halfLength:].tolist());\n",
    "            root.bottomLeft = self.construct(array(grid)[halfLength:, :halfLength].tolist());\n",
    "            root.bottomRight = self.construct(array(grid)[halfLength:, halfLength:].tolist());\n",
    "        return root;\n",
    "                    \n",
    "    def allValueSame(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: boolean\n",
    "        \"\"\"\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[0][0] != grid[i][j]:\n",
    "                    return False;\n",
    "        return True;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def construct(self, grid: List[List[int]]) -> 'Node':\n",
    "        def is_eq(src):\n",
    "            first=src[0][0]\n",
    "            for x in src:\n",
    "                for y in x:\n",
    "                    if y!=first:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        import numpy\n",
    "        mid=len(grid)//2\n",
    "        grid=numpy.array(grid,dtype=int)\n",
    "        topleft=grid[:mid,:mid]\n",
    "        if len(topleft)==0: return Node(0,True)\n",
    "        topright=grid[:mid,mid:]\n",
    "        bottomleft=grid[mid:,:mid]\n",
    "        bottomright=grid[mid:,mid:]\n",
    "\n",
    "        topleft_eq=is_eq(topleft)\n",
    "        topright_eq=is_eq(topright)\n",
    "        bottomleft_eq=is_eq(bottomleft)\n",
    "        bottomright_eq=is_eq(bottomright)\n",
    "\n",
    "        if is_eq(grid):\n",
    "            return Node(topleft[0][0],True)\n",
    "\n",
    "        if len(topleft)==1:\n",
    "            if topleft[0][0]==topright[0][0] and bottomleft[0][0]==bottomright[0][0] and topleft[0][0]==bottomright[0][0]:\n",
    "                return Node(\n",
    "                    topleft[0][0],\n",
    "                    True\n",
    "                )\n",
    "            else:\n",
    "                return Node(\n",
    "                    topleft[0][0],\n",
    "                    False,\n",
    "                    Node(topleft[0][0],True),\n",
    "                    Node(topright[0][0],True),\n",
    "                    Node(bottomleft[0][0],True),\n",
    "                    Node(bottomright[0][0],True)\n",
    "                    )\n",
    "        print(topleft_eq,topright_eq)\n",
    "        return Node(\n",
    "            topleft[0][0],\n",
    "            False,\n",
    "            Node(topleft[0][0],True) if topleft_eq else self.construct(topleft),\n",
    "            Node(topright[0][0],True) if topright_eq else self.construct(topright),\n",
    "            Node(bottomleft[0][0],True) if bottomleft_eq else self.construct(bottomleft),\n",
    "            Node(bottomright[0][0],True) if bottomright_eq else self.construct(bottomright),\n",
    "        )\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
